Problem Solving/BFS
백준 5427: 불 - BFS
https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 전체 와일문 도는 것이 1초이고 현재까지 몇 초인지 변수에 저장해둡니다. 그 뒤 불을 번지게 하고 상근이를 이동시킵니다. (queue 첫 번째의 time 값이 위에서 저장해둔 시간 변수가 아니게 될 때가지만) 불을 킬 때는 벽인지 아닌지만 검사해야하고, 상근이를 이동 시킬 때는 불이 번진 위치인지도 확인해주어야 합니다. 만약 상근이가 2차원 배열 테두리에 도달하게 되면 탈출에 성공하게 됩니다. # Pypy3 ..
백준 11967: 불 켜기 - BFS
현재 방에서 스위치를 통해 불을 킨 후, 인접해 있는 방 중 불이 켜져있는 방에 들어가 스위치를 키게 끔 하였습니다. 이 것을 한 주기라고 보고, 한 주기에서 불을 킨 적이 있다면, 다시 1,1 부터 새롭게 들어갈 수 있는 방을 확인하게끔 하였습니다. 한 번 불을 켰다면 다시는 불을 키지 않아도 되게끔 'swithced_turned'라는 변수로 체크해 두었고, 이는 초기화 되지 않습니다. 새롭게 불이켜진 방이 있고, 그 방은 현재 이동 가능한 방과 인접해 있어 이동할 수 있는 경우가 될 수 있습니다. 따라서 매 주기마다 계속 이전에 와 봤던 방이라도 확인을 해주어야 하기 때문에 'visited'는 주기마다 초기화를 해주었습니다. 불을 켤 때 마다 count를 해주고, 주기가 끝날 때마다 'total_co..
백준 3197: 백조의 호수 - BFS
https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net python3로 돌릴 경우 시간초과가 나기 때문에 pypy3로 제출하였습니다. 이 문제는 아무 생각 없이 BFS를 돌리게 되면 시간 초과가 납니다. 우선 백조가 만나는 지 체크하는 것과, 물을 녹이는 것을 한 주기라고 생각합니다. queue를 몇 개 더 추가하여, 물을 녹이기 전 백조가 만나는 지 체크하고, 만나지 않는 다면 물을 녹이는 일을 하 되, 다음 주기 때의 ..
백준 2636: 치즈 - BFS
https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net (0, 0)를 시작으로 bfs를 돌리면서 0을 만나면 queue에 넣고 가장자리에 있는 치즈를 만나면 0으로 바꾼 뒤 queue에는 넣지 않으면 가장자리에 있는 치즈만 녹이는 것이 가능합니다. (visited는 모두 체크) bfs를 돌면서 가장자리의 치즈를 만나면 count를 해주고 완료 후에는 count를 return해주어 마지막에 모든 치즈가 녹기 전에 몇 개가 있었는지 알 수 있습니다. from sys impo..