문제 링크
https://www.acmicpc.net/problem/9376
🛠️ 미해결
- 풀이시간 : 2시간 이상
- 틀린 이유 :
- 문제 풀이 방법에 접근하지 못함 : 애초에 문제 풀이 방법 자체에 접근하지 못했다... BFS 문제인거 같아서 계속해서 차원을 나누어보기도 하고 했지만 중복 방문이 되면 안되기 때문에 한 차원내에서 해결해야 했고 0-1 BFS 개념 자체를 처음 접한 나한테는 너무 어려웠다.
- 0-1 BFS : 0-1 BFS 자체는 어려운 개념이 아니다 한 차원에서 먼저 방문에 우선순위를 설정하는 것이다. 즉 deque에 다음의 방문 가능한 곳을 담을 때, 맨 앞쪽에 우선순위가 높은 것을 전부 방문 후, 다음 방문이 가능하도록 맨 앞쪽에 담는 것이다.
- 누적 배열의 초기화 : 0-1 BFS를 모르고 있었다고 해도 알고 난 다음에도 계속해서 틀렸다. 그 이유는 다음과 같다. 모든 죄수는 밖으로 나갈 수 있는 경우만 존재하므로 사실상 벽을 제외하더라도 모든 죄수들은 밖을 통해서든 안을 통해서든 이어져 있다고 생각할 수 있다. 그렇기에 모든 방문가능한(문 포함)은 0 이상의 값을 가진다. 그럼 왜 틀렸는가? 모든 3명의 방문 값을 누적하는 배열을 0으로 초기화한 것 까지는 좋았으나 -1을 누적 조건에서 빼버린 것이다. 그렇기에 핵심인 각 문의 경우 누적해서 3번씩 열렸으니 중복된 2번을 빼야한다는 조건 이후에 0이상인 조건에서 걸려야하는데 -1인 조건을 빼버렸으니 계속 틀린 값이 나온것이다. 왜 이걸 깜빡했는가? 해당 문제의 본질인 0이상이라는 점을 인지를 못하고 있던점이 가장 크다. 이 조건에 대해 깨달았다면 애초에 이러한 조건으로 틀리지도 않았을 것이다.
- 3명의 방문의 아이디어 : 해당 아이디어 자체는 처음 접해보기 때문에 한번쯤 고려해둘 아이디어로 생각해두는게 좋을 거 같다. 물론 0-1 BFS를 이제는 알고 있다는 전제하지만 말이다.
🕒 Python 풀이시간: 미해결
from collections import deque
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
def bfs(x, y):
visited = [[-1] * (w + 2) for _ in range(h + 2)]
q = deque()
q.append((x, y))
visited[x][y] = 0
while q:
now = q.popleft()
for i in range(4):
nx = now[0] + dx[i]
ny = now[1] + dy[i]
if nx < 0 or ny < 0 or nx >= h + 2 or ny >= w + 2:
continue
if visited[nx][ny] != -1:
continue
if board[nx][ny] == '*':
continue
if board[nx][ny] != '#':
visited[nx][ny] = visited[now[0]][now[1]]
q.appendleft((nx, ny))
else:
visited[nx][ny] = visited[now[0]][now[1]] + 1
q.append((nx, ny))
return visited
for tc in range(int(input())):
h, w = map(int, input().split())
prisoners = []
board = [['.'] * (w + 2) for _ in range(h + 2)]
for i in range(1, h + 1):
arr = list(input())
for j in range(1, w + 1):
if arr[j - 1] == '$':
prisoners.append((i, j))
board[i][j] = arr[j - 1]
# 각각의 BFS 실행 후 누적
resultVisited1 = bfs(prisoners[0][0], prisoners[0][1])
resultVisited2 = bfs(prisoners[1][0], prisoners[1][1])
resultVisitedOutside = bfs(0, 0)
# 최소 비용 계산
result = 1e9
for i in range(h + 2):
for j in range(w + 2):
if board[i][j] == '*': # 벽인 경우 무시
continue
total_cost = resultVisited1[i][j] + resultVisited2[i][j] + resultVisitedOutside[i][j]
if board[i][j] == '#': # 문인 경우 중복되는 비용 -2 처리
total_cost -= 2
if total_cost >= 0: # 유효한 경로만 고려
result = min(result, total_cost)
print(result)
이렇게 Python으로 백준의 "탈옥" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
