https://www.acmicpc.net/problem/14940 오랜만에 코테를 풀어보러 왔다.어떤 문제를 풀까 하다가 solved.ac 클래스에 새롭게 선정된 문제를 선택했다.쉽게쉽게 실버1로 선택하였지만 Python으로 풀어보는 코테는 처음이었다. 문제는 전혀 어렵지 않고 모든 지점에서부터 목적지의 최단거리를 구하는 것이다.bfs를 수행하고 visit 배열을 출력하면 된다. 어려운 부분은 없었지만 출력 조건이 헷갈렸다.우선 입력은 아래와 같다.0: 갈 수 없는 땅1: 갈 수 있는 당2: 목적지 출력은0: 원래 갈 수 없는 땅-1: 도달할 수 없는 땅나머지는 최단 거리이다. 각 경우만 잘 따지면 어렵진 않다. 오히려 국어가 어려웠던 문제. import sysimport queuedef bfs(): ..
Algorithm/BFS
https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net BFS 문제다. 이 문제를 푸는데 2~3일 정도 걸렸다. 문제는 백조 두 마리가 존재하고 이 백조들이 만나는 데까지 소요되는 날을 구하는 문제다. 이 사이에는 얼음이 존재하고, 이 얼음은 물과 접촉해 있을 때 녹는다. 처음 생각한 방법은 단순하게 얼음을 녹이고, 백조의 경로를 찾고를 반복하는 것이었다. 구현해볼 것도 없이 시간 초과가 날 것이기 때문에 바로 패스했다. ..
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로 접근했다. 구현 요소도 포함된 것 같다. 재방문이 필요하다는 점에서 고민 요소가 있었다. 조건 없이 계속 재방문 하면 무한 루프가 돌거나 돌지 않아도 메모리가 터질 것이다. 무한 루프를 막기 위해 방문 시 들고 있던 돈을 기준으로 재방문 여부를 결정했다. 방에 들어와서 소지하게 된 돈이 이전에 방문했을 때의 돈을 비교해서 ..
