본문 바로가기

알고리즘 ·코딩 공부/백준 온라인 문제 풀이

 (29)
[BFS] BJ2206, BJ11442, BJ16933, BJ16946 벽 부수고 이동하기 1, 2, 3 ,4 문제 출처: 벽 부수고 이동하기 1 : https://www.acmicpc.net/problem/2206 벽 부수고 이동하기 2 : https://www.acmicpc.net/problem/14442 벽 부수고 이동하기 3 : https://www.acmicpc.net/problem/16933 벽 부수고 이동하기 4 : https://www.acmicpc.net/problem/16946 Problem 이번 문제는 일반적인 최단 경로 찾기 문제에서 시리즈로 조금씩 조건이 추가되거나 응용되는 문제들이다. 최단 경로 찾기 문제 관련 여러 가지 유형을 재밌게 익힐 수 있었다. Solution 1번 : BFS로 최단 거리 탐색을 하되, 벽을 부술 수 있기 때문에 이미 부순 경우와 부수지 않은 경우를 나눠 탐색한다..
[BFS] BJ16236 아기 상어 문제 출처: https://www.acmicpc.net/problem/16236 Solution BFS로 아기 상어가 먹을 수 있는 물고기를 탐색하여 최단 거리를 구하는 과정을 반복하며 몇 초간 이동할 수 있는지 구한다. Point BFS 탐색을 여러번 하면서 물고기를 먹을 수 있을 때까지 해당 물고기까지의 최단 거리를 구해 모든 거리의 총 합을 구하는 문제이다. 주의할 점은 먹을 수 있는 물고기가 여러마리 일 때, 거리가 같으면 위쪽에 있을 수록, 왼쪽에 있을수록 우선 순위가 높다는 것인데, 이걸 고려해서 구현하는게 은근 까다롭다. 문제 유형으로 보면, BFS에서 같은 거리에 있는 점들을 특정한 우선 순위에 따라 처리하는 문제로 볼 수 있는데, 기본 BFS는 거리가 같은 점들에 대해서는 특별한 우선 순..
[시뮬레이션] BJ16235 나무 재테크 문제 출처: https://www.acmicpc.net/problem/16235 Solution 현재 땅의 영양 상태, 추가 영양, 죽은 나무 정보를 배열에 넣고, 나무 정보를 원소가 vector인 배열에 넣어 K 횟수만큼 시뮬레이션을 돌린다. Point 봄에 나무가 어린 순서로 영양분을 먹기 때문에 sort가 필요한데, map이나 pq같은 자료 구조를 쓸 수도 있지만 단순히 sort를 써도 풀리는 문제였다. 처음에 죽은 나무를 살아 있는 나무와 똑같이 vector 배열에 넣고 했더니 시간 초과가 나서, 단순히 2차원 배열에 추가될 양분을 봄에 미리 계산해서 더하기만 하는 식으로 바꿔서 시간을 단축했다. #include #include #include using namespace std; int N, M..
[BFS] BJ16234 인구 이동 문제 출처: https://www.acmicpc.net/problem/16234 Solution BFS로 동맹국들을 찾아 동맹국끼리 묶고, 인구 이동하여 값을 갱신하는 과정을 반복한다. Point 동맹국이 여러개 생길 수 있다는 점을 주의해야한다. 따라서 BFS를 할 때, BFS 호출 횟수에 따라 k값을 증가시키며 k값을 동맹의 id로 사용했다. 처음에 BFS를 할 때마다 인구 이동을 해서 a를 갱신했는데, 그렇게 하면 시간 초과가 난다. 따라서 전체 a의 동맹국을 모두 확인해서 visit에 넣어두고, 해당 동맹의 인구수를 ppp에 넣고 동맹국 수를 ccc에 넣어 나중에 한번에 인구 이동을 하도록 최적화했다. #include #include #include using namespace std; int N..
[DFS] BJ15686 치킨 배달 문제 출처: https://www.acmicpc.net/problem/15686 Solution DFS로 닫을 가게를 고르고, 그 때의 치킨 거리를 구해서 최소 값을 갱신해나간다. Point 문제의 조건에는 닫지 않을 가게의 수 M이 주어지지만, 가게 정보가 2로 주어지므로, 닫지 않을 가게(c.size()-M)를 고르는 것이 더 편하다. DFS 탐색에서 경우의 수를 고를 때, for 문의 i를 cc부터 하는 것이 효율적이다. 거리 계산할 때, 복잡하게 BFS 같은 탐색 생각하지 말고 직관적으로 바로 구하는 것이 더 낫다. #include #include #include #include using namespace std; int N, M; int map[50][50]; vector c; vector h..
[시뮬레이션] BJ15685 드래곤 커브 문제 출처: https://www.acmicpc.net/problem/15685 Solution 입력 받은 드래곤 커브를 그리고, 사각형 개수를 센다. Point 커브를 그리는게 조금 난해한데, 지금까지 지나온 길의 방향을 모두 기억하고 (dir), 반대 순서로((dir.size()-1)~0) 반 시계 방향으로 돌린 방향((dir[k]+1)%4)으로 그리면 된다. 주의할 점은, 0세대 그리는 부분을 놓치지 말고 잘 해줘야 한다는 것이다. #include #include using namespace std; struct curve { int r, c, d, g; }; int N; vector dir; vector curves; int map[102][102]; int dr[] = { 0, -1, 0, 1 ..
[DFS] BJ15684 사다리 조작 문제 출처: https://www.acmicpc.net/problem/15684 Solution DFS 탐색으로 사다리를 추가할 칸을 고르고 해당 map 상태에서 주어진 조건을 만족하는지 확인한다. Point 사다리 설치 개수를 0~3개로 하나씩 늘려가며 해당 개수에서 조건을 만족하는지 확인한다. 사다리 상태에서 조건을 체크하는 부분에서 처음에 BFS 같은 방법으로 탐색하려고 했는데, 시간이 너무 오래 걸려 시간 초과가 났다. 단순히 조건만 확인하면 되므로 사다리를 탈 때 열 상태만 확인하면 된다. DFS 탐색에서도 for문의 r을 1부터 시작해서 시간 초과가 났는데, 사다리를 하나 고르면 그 이전 r은 확인할 필요가 없으므로 r부터 다시 시작하도록 했다. 시간이 tight한 문제여서 여러 가지 최적화를..
[DFS] BJ15683 감시 문제 출처: https://www.acmicpc.net/problem/15683 Solution DFS 탐색으로 각 감시 카메라의 방향을 완전 탐색하고, 각 카메라의 속성에 따라 감시 지역을 구하여 사각 지대를 구하며 최소 값을 갱신한다. Point DFS 완전 탐색은 어렵지 않았으나 각 카메라의 방향이 정해진 뒤 감시 구역을 구하는 것이 까다로웠다. BFS와 비슷한 로직으로 전진 방향에 대한 감시 구역을 구하도록 했다. vision() 함수에서 카메라 속성에 따라 여러 방향으로 search() 함수를 각각 수행하도록 했는데, search() 함수에서 한번에 처리하게 하면 더 빠르게 동작할 것 같다. #include #include #include #include #include using namespa..

티스토리툴바