[백준] 2206번 벽 부수고 이동하기 (파이썬)

 

문제

 

2206번: 벽 부수고 이동하기

 

 

 

정답 소스코드 (Python)

 

from collections import deque
n,m=map(int,input().split())
field=[]
for i in range(n):field.append(list(map(int,list(input()))))
visited=[[[0 for k in range(2)] for i in range(m)]for j in range(n)]
wall_break=0
dx=[0,0,1,-1]
dy=[1,-1,0,0]

def bfs(start_x,start_y):
    global wall_break
    level=1
    q=deque([[start_x,start_y,level,wall_break]])
    visited[start_y][start_x][wall_break]=level

    while q:
        x,y,level,wall_break=q.popleft()
        
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<m and 0<=ny<n:

                if field[ny][nx]==0 and visited[ny][nx][wall_break]==0:
                    visited[ny][nx][wall_break]=level+1
                    q.append([nx,ny,level+1,wall_break])
                elif field[ny][nx]==1 and wall_break==0:
                    visited[ny][nx][wall_break+1]=level+1
                    q.append([nx,ny,level+1,wall_break+1])


bfs(0,0)
if visited[n-1][m-1][wall_break]:print(visited[n-1][m-1][wall_break])
else:print("-1")

 

 

풀이  (Python)

 

 

 

Point 1)  BFS(너비 우선 탐색)

def bfs(start_x,start_y):
    global wall_break
    level=1
    q=deque([[start_x,start_y,level,wall_break]])
    visited[start_y][start_x][wall_break]=level

    while q:
        x,y,level,wall_break=q.popleft()
        
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<m and 0<=ny<n:

                if field[ny][nx]==0 and visited[ny][nx][wall_break]==0:
                    visited[ny][nx][wall_break]=level+1
                    q.append([nx,ny,level+1,wall_break])
                elif field[ny][nx]==1 and wall_break==0:
                    visited[ny][nx][wall_break+1]=level+1
                    q.append([nx,ny,level+1,wall_break+1])

 

최단 거리를 구하는 문제이므로, bfs를 선택하여 풀이하였다. 한 칸 움직일 때마다 level을 +1해 주어서 visited배열에 넣어주었다. visited배열은 0인 경우 방문하지 않은 경우 이고, 0이 아닌 경우 방문한 배열로 써 결과도 저장할 수 있게 사용하였다.

 

dx, dy리스트로 갈 수 있는 방향을 for문으로 간결하게 표현하여 if문으로 갈 수 있는 범위를 지정해서 움직이도록 하였다.

 

 

핵심 부분은 아래의 조건문이다.

if field[ny][nx]==0 and visited[ny][nx][wall_break]==0:
    visited[ny][nx][wall_break]=level+1
    q.append([nx,ny,level+1,wall_break])
elif field[ny][nx]==1 and wall_break==0:
    visited[ny][nx][wall_break+1]=level+1
    q.append([nx,ny,level+1,wall_break+1])

 

첫 번째 조건: 0인 길이면서 방문하지 않은 경우 -> visited에 level+1을 추가, 큐에 해당 좌표와 level을 push

두 번째 조건: 1인 벽이면서 여태 벽을 부순 적이 없는 경우-> visited에 해당 벽 칸에 level+1을 추가

 

 

 

visited을 처음 초기값부터 3중배열로 선언한다.

why? 벽을 부수기 전과 후의 visited배열을 다른 것을 사용해야 한다.

한 개의 visited배열로는 생각보다 신경 써야 할 부분들이 중첩되어 풀이할 수 없다.

 

visited=[[[0 for k in range(2)] for i in range(m)]for j in range(n)]

 

벽을 부수기 전에는 visited[][][0] 리스트를 사용하지만, 벽을 부수는 경우 visited [][][1]로 변경