본문 바로가기
댓글 달기 글쓰기
[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] SWEA1767 프로세서 연결하기 문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf Solution DFS 탐색으로 각 프로세서의 연결 방향을 결정하고, 해당 연결에서의 거리를 구해, 가장 많은 프로세서를 연결했을 때 최소 거리를 구해간다. Point 문제의 특이사항은, 연결 개수는 최대화하면서, 연결 거리는 최소화해야하기 때문에 두 가지 결과를 모두 고려해야한다는 점이다. 처음에 모든 프로세서의 연결 방향을 다 정하고 나서 거리를 계산했는데, 그렇게 하면 연결 방향 고려할 때, 모든 경우의 수를 Brute Force하게 되기 때문에 시간 초과가 난다. 따라서, 특정 프로세서에서 네 방향 모두 연결이 불가능하..
[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 ..

티스토리툴바