2206. 벽 부수고 이동하기

문제 링크

2206. 벽 부수고 이동하기

문제 코드

from collections import deque

num_list = list(map(int, input().split()))

row = num_list[0]
col = num_list[1]

maze = [[0 for i in range(col)]for j in range(row)]
visited = [[[0 for k in range(2)] for i in range(col)]for j in range(row)] #벽을 부술때와 안부술때 visited를 따로 관리해줘야함 

for i in range(row):
    tmp_row = input()
    for j in range(col):
        maze[i][j] = tmp_row[j]

que = deque()

visited[0][0][0] = 1
visited[0][0][1] = 1
que.append([0,0,0,1])

result = 10000001
while len(que)>0:
    now = que.popleft()
    x = now[0]
    y = now[1]
    break_checker = now[2]
    count = now[3]

    if x == row-1 and y == col-1 :
        if result > count:
            result = count

    # up,down,left,right
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]

    for i in range(4):
        if 0<=x+dx[i]<row and 0<=y+dy[i]<col :
            if break_checker == 1 : # 벽을 한번 부쉈을때
                if maze[x + dx[i]][y + dy[i]] == '0' and visited[x+dx[i]][y+dy[i]][1] == 0:
                    visited[x + dx[i]][y + dy[i]][1] = 1
                    que.append([x + dx[i], y + dy[i], break_checker, count + 1])
            else : #벽을 한번도 안부쉈을때
                if maze[x + dx[i]][y + dy[i]] == '0' and visited[x + dx[i]][y + dy[i]][0] == 0:
                    visited[x + dx[i]][y + dy[i]][0] = 1
                    que.append([x + dx[i], y + dy[i], break_checker, count + 1])

                elif break_checker == 0 and visited[x + dx[i]][y + dy[i]][1] == 0:
                    visited[x + dx[i]][y + dy[i]][1] = 1
                    que.append([x + dx[i], y + dy[i], 1, count + 1])


if result == 10000001:
    result = -1
print(result)

문제 풀이

• 기초적인 그래프 탐색처럼 상하좌우 이동을 넣고, break_checker가 0이면 1인경우에도 이동할수 있도록 처음에 구현
• bfs로 구현하고 visited가 단일일 경우에 해결 못하는 case 발생
  00000
  11110
  00000
  01111
  00010
  answer = 9
  wrong = -1
• 벽을 부술경우와 부수지 않을 경우 방문 경로를 다르게 저장해야한다는 것을 알게됨
• visited를 3차원으로 관리해서 방문경로를 저장할수 있게함
• 이 경우 결과값이 2개 이상이 나오기때문에 최종적으로 가장 적은 length를 돈것을 출력할수 있도록 해줘야함
• 모든 경로를 다 돌수 있게 해주고, length의 minimum을 출력할수 있도록 해줌