https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문 www.acmicpc.net BFS와 구현 문제다. BFS와 동일하게 진행하고, 움직일 때 범위 검사만 추가해서 했다. 회전에 대해서는 방문 배열을 3차원으로 생성해 가로일 때 방문과 세로일 때 방문을 구분해서 체크했다. 회전시 계산이 편하도록 3칸 중 중간 칸을 기준으로 삼았다. #include #include using namespace std; // 상하좌우 탐색을 위함 int dr[4] = { ..
Algorithm/BFS
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net BFS 문제다. 말이 되고픈 원숭이와 비슷하다. https://abbiddo.tistory.com/16 만날 때마다 새롭다. 특수 경우가 방문한 곳을 일반적인 경우로 방문할 수 있어야 한다는 점이 항상 헷갈리게 한다. 방문 배열을 3차원으로 만들고 [r][c][0]에는 벽을 뚫고 가지 않은 경로 / [r][c][1]에는 벽을 뚫고 간 경로를 저장했다. 초기값은 벽이 아니기..
https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net BFS 문제다. 문제를 해결하기 위해 돌아온 길이 많아서 시행착오는 후에 작성하겠다. 문제 해결은 일반 BFS에 8방향 검사를 추가로 시행했다. 방문 배열을 3차원으로 설정해 8방향 이동 능력을 몇 번 사용했는지 체크했다. 간단한데도 이 방법을 생각해내는데 오래 걸렸다... 그리고 이 문제에서 오류가 발생하기 쉬운 점은 입력이 세로 가로가 아닌 가로 세로인 점이다. 세로를 먼저 입..
https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net BFS 문제다. 처음 떠올린 방법은 덩어리를 찾아 덩어리 별로 같은 숫자로 저장하는 것이다. 그 후 각 덩어리의 테두리로부터 본인 숫자보다 큰 덩어리에 닿는 경우의 수를 모두 찾은 후 최솟값을 출력하는 것이다. 시간이 오래 걸릴 것 같아 최대한 반복을 덜 돌리려고 고민을 했다. 모든 경우의 수를 찾지 않고, 다리의 최소 길이보다 이동 수가 많아지면 함수를 바로 종료하는 것이다. 그리고 테두리를 따로 구..
https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net BFS 문제다. 문제 이해에 이틀을 쓴 것 같다...ㅋ 불도 사람처럼 1분에 한 칸만 움직이는 줄 알았는데 불은 1분에 4방향으로 다 퍼지는 것이었다. 이 부분을 해결하고 나니 첫 번째 의문은 해결됐고 다른 의문이 생겼다. 몇 분이 걸리는지가 중요한 문제이기 때문에 한 타임에 딱 한 번만 움직여야 하는데 그 부분 구현이 의문이었다. 나는 큐의 사이즈를 구한 후 그만큼만 돌리면 된다고..
https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net BFS와 구현이 함께 있는 문제다. 문제의 알고리즘 분류를 보니 DFS로도 풀 수 있는 것 같다. 그림 문제처럼 덩어리를 파악하고 치즈 문제처럼 배열 전체에 BFS를 적용하는 횟수를 구해야 한다고 생각했다. 경험이 있는 문제들의 응용 문제 같아서 알고리즘이 쉽게 떠올랐다. 이 문제의 주의점은 올해(?) 녹은 빙산이 0이 되어 다른 빙산에 영향을 주면 안된다는 것이다. 이걸 해결하기 위해서는 ..
