https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net BFS 문제다. 이 문제를 푸는데 2~3일 정도 걸렸다. 문제는 백조 두 마리가 존재하고 이 백조들이 만나는 데까지 소요되는 날을 구하는 문제다. 이 사이에는 얼음이 존재하고, 이 얼음은 물과 접촉해 있을 때 녹는다. 처음 생각한 방법은 단순하게 얼음을 녹이고, 백조의 경로를 찾고를 반복하는 것이었다. 구현해볼 것도 없이 시간 초과가 날 것이기 때문에 바로 패스했다. ..
Algorithm/BFS
https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net BFS 문제다. 벽에서 갈 수 있는 칸들을 세는 문제다. 모든 벽에서 BFS를 돌리면 빈 칸을 여러 번 방문하기 때문에 시간초과가 날 것이다. 빈 칸의 영역을 찾아서 크기를 구한 뒤 배열에 저장해뒀다. 그 후 배열을 전체 탐색 하면서 벽인 경우 4방향을 검사해 갈 수 있는 영역의 크기를 더했다. 이 때 이어져 있는 영역이 존재할 수 있으므로, 영역을 찾을 때 영역의 번호를 부..
https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 비트마스킹을 이용한 BFS 문제다. 흔히 우리가 아는 2차원 배열에서 영역을 구하는 문제다. 그러나 인접한 모든 곳으로 지나갈 수 있는 것이 아니고 벽으로 막혀 있는 방의 영역을 구하는 문제다. 이 문제의 특징은 막힌 칸이 있는 것이 아니라 인접한 방 사이를 갈 수 없는 벽이 존재한다. 따라서 입력이 2차원 배열의 크기만큼 각 칸의 벽을 나타내는 정수가 들어온다. 좌1 상2 우4 하8로 2의..
https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net BFS문제다. 일반 미로 문제에서 벽(검은방)을 부수고 갈 수 있는 미로로 생각하면 되는 문제다. 문제에서 구해야하는 건 미로의 최단 경로가 아닌 최대한 벽을 적게 만나는 경로를 찾는 것이다. 방문 배열을 이용해서 문제를 해결했다. 방문 배열에 지나간 검은 방의 개수를 저장하고 현재 이동하려는 방 까지의 검은 방의 개수가 이전에 방문했을 때의 검은 방의 개수보다 작다면 방문한다. 이 때 간과했던 ..
https://www.acmicpc.net/problem/2310 2310번: 어드벤처 게임 입력은 여러 개의 미로로 주어진다. 각 미로의 첫 줄에는 미로의 방 수를 나타내는 정수 n(1 ≤ n ≤ 1000)이 주어진다. 다음 n 줄에는 각 방의 정보가 주어진다. 각 방의 정보는 방의 내용물을 나타 www.acmicpc.net BFS 문제다. DFS도 가능할 것이라고 생각하나 BFS로 접근했다. 구현 요소도 포함된 것 같다. 재방문이 필요하다는 점에서 고민 요소가 있었다. 조건 없이 계속 재방문 하면 무한 루프가 돌거나 돌지 않아도 메모리가 터질 것이다. 무한 루프를 막기 위해 방문 시 들고 있던 돈을 기준으로 재방문 여부를 결정했다. 방에 들어와서 소지하게 된 돈이 이전에 방문했을 때의 돈을 비교해서 ..
https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net BFS 문제다. https://abbiddo.tistory.com/12 불!과 비슷한 문제다. 같은 상황에 출구가 정해져 있고, 돌이 있다는 점에서만 차이가 있기 때문에 설명은 생략 #include #include using namespace std; int n, m; char board[50][50]; bool gisit[50][50];// 고슴도치의 방문 체크 bool wisit[50][50];// 물의 ..
