[백준-파이썬] 2206: 벽 부수고 이동하기

문제 보러 가기~~

아이디어 ✨

BFS인데 3차원 리스트를 활용해야 한다.
문제에서 3차원 리스트 쓰는 건 처음 해봤다 !!

일반적인 최단 거리 찾기에서 벽을 최대 한번 부술 수 있다는 조건이 추가되었다.
그래서 벽을 부수었는지 여부에 따라서 다른 2차원 리스트로 방문 체크를 해줬다. (즉 3차원 리스트를 만듦)

큐에 해당 인덱스, 벽을 부수었는지, 출발점부터 해당 위치까지의 거리를 넣어줬다.
큐 안에 요소가 있을 때, 하나씩 꺼내보면서
도착이면 그걸 따로 저장해줬고
그게 아니라면 4면을 돌아보면서 범위 이내인지 체크한다.
방문을 하지 않았고 벽인데, 아직 한번도 벽을 부수지 않았다면 벽을 부수고 거기로 간다.
방문을 하지 않았고 길이면, 벽을 부수지 않고 거기로 간다.

'거기로 간다'라는 것은 (인덱스, 벽을 부수었는지 여부, 출발점~해당위치 거리)를 큐에 넣는다는 뜻이다. 큐에 요소를 넣기 전에 방문 체크를 해주었다.

출발점은 (1, 1), 도착점은 (N, M)라고 해서 인덱스를 편하게 쓰려고 패딩을 만들었다.

코드 👩‍💻

import sys, collections

input = sys.stdin.readline

# 4방향 상하좌우
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

N, M = map(int, input().split())
map = [[1] * (M + 2)] + list([1] + list(map(int, input().rstrip())) + [1] for _ in range(N)) + [
    [1] * (M + 2)]  # 인덱스 편하게 쓰려고
visit = [[[0] * (M + 2) for _ in range(N + 2)] for _ in range(2)]  # 벽 부셨는지 여부, 방문 체크 - i, j

Q = collections.deque()
Q.append((1, 1, 0, 1))  # 출발점의 인덱스, 벽 부셨나(0 or 1), 거리

ans = []

while Q:
    i, j, canBreak, distance = Q.popleft()

    visit[canBreak][i][j] = 1  # 방문 체크

    if i == N and j == M:  # 도착이면
        ans.append(distance)

    for k in range(4):
        ni = i + direction[k][0]
        nj = j + direction[k][1]

        if 0 < ni < N + 2 and 0 < nj < M + 2:  # 범위 이내이고
            if visit[canBreak][ni][nj] == 0 and map[ni][nj] == 1 and canBreak == False:  # 방문 안했고, 벽인데 갈 수 있다면 가보기
                Q.append((ni, nj, 1, distance + 1))

            if visit[canBreak][ni][nj] == 0 and map[ni][nj] == 0:  # 방문 안했고 길이면
                Q.append((ni, nj, canBreak, distance + 1))  # 벽 안 부수고 가보기

if ans:
    print(min(ans))  # 벽 부수고, 안 부수고 둘 다 도달 가능하면 그 중 최소값을 답으로
else:
    print(-1)  # 못 도달하는 경우

그런데 계속 시간 초과가 나왔다..
나는 큐에서 빼낼 때 방문 체크를 했는데, 그러면 같은 위치가 여러 번 큐에 들어갈 수도 있기 때문이었다. 그래서 아래와 같이 큐에 넣을 때 방문 체크를 하는 걸로 바꾸었더니 성공했다 ! ㅎㅎ

그리고 if visit[1][ni][nj] == 0 and map[ni][nj] == 1 and canBreak == 0: 이 부분도 위에서는 잘못 썼다는 걸 깨달았다 !
if visit[canBreak][ni][nj] == 0였는데 if visit[1][ni][nj] == 0로 바꿨다.

canBreak == False였는데, 물론 의미가 통하기는 하지만 0이나 1로 표현하려고 했어서, 더 정확히 canBreak == 0 으로 바꿨다.

if 0 < ni < N + 2 and 0 < nj < M + 2:  # 범위 이내이고
            if visit[1][ni][nj] == 0 and map[ni][nj] == 1 and canBreak == 0:  # 방문 안했고, 벽인데 갈 수 있다면 가보기
                visit[1][ni][nj] = 1  # 방문 체크
                Q.append((ni, nj, 1, distance + 1))

            if visit[canBreak][ni][nj] == 0 and map[ni][nj] == 0:  # 방문 안했고 길이면
                visit[canBreak][ni][nj] = 1  # 방문 체크
                Q.append((ni, nj, canBreak, distance + 1))  # 벽 안 부수고 가보기