[백준] 2206 파이썬(python) : 벽 부수고 이동하기 - (3중 리스트)

2206번 : 벽 부수고 이동하기

 

 

전 포스팅에서 풀었던 bfs문제(2178번 미로탐색)에 조건을 하나 더 추가한 문제이다. 지금의 나로선 새로운 조건을 추가한것을 구현하는데 상당히 어렵고 답을 이해하는것도 힘들었다. 더 정진하겠다.

 

import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
graph = [ list(map(int, sys.stdin.readline().strip())) for _ in range(n) ] #1
visited = [[ [0, 0] for _ in range(m) ] for _ in range(n) ] #2
visited[0][0][0] = 1 #3
dx = [ 0, 0, -1, 1 ]
dy = [ -1, 1, 0, 0 ]

def bfs():
    q = deque()
    q.append([0, 0, 0]) #4
    while q:
        x, y, wall = q.popleft() #5
        if x == n-1 and y == m-1: #6
            return visited[x][y][wall]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and visited[nx][ny][wall] == 0: #7
                if graph[nx][ny] == 0: #8
                    visited[nx][ny][wall] = visited[x][y][wall] + 1
                    q.append([nx, ny, wall])
                elif graph[nx][ny] == 1 and wall == 0: #9
                    visited[nx][ny][1] = visited[x][y][wall] + 1
                    q.append([nx, ny, 1])
    return -1 #10
print(bfs())

 

벽을 부순상태와 안부순상태를 구분해야하는데 입력을 받는 graph리스트에서는 그것을 처리할 수 없다. (입력값을 바꿀 수 없기 때문에) 그래서 방문처리를 해주는 visit을 3차원배열로 만들어 구분한다.

3차원 배열 visit에서 변수 wall은 인덱스를 의미하고 인덱스에서만 사용, visit[x][y][0]은 벽을 부수지 않은 상태, visit[x[y][1]은 벽을 부순상태(한번 1이 되면 그 이후로 쭉 wall = 1을 유지)

 

#1: 그래프의 값 입력

#2: 벽 부순상태, 안부순상태를 나누기 위한 인덱스 2개로 3차원 배열 생성 [ 0, 0 ]

#3 : 처음 장소 방문처리, 처음 위치는 벽이 없는 위치 일테니 인덱스 0(wall=0) 처음 방문 자리도 포함해야하며 안하면 원하는 값에서 1낮은값이 출력됨

#4: 처음장소(0, 0)랑 wall = 0으로 해서 초기값 저장

#5 : 리스트에 있는 가장 왼쪽 값 각각 꺼냄

#6 : 반복문 탈출조건, 마지막 위치에 도착하면 최단거리 출력, (n-1, m-1)위치와 함께 벽(wall)이 0인지 1인지 알아야 하기 때문에 return문으로 작성

#7 : 새로운 방향이 그래프의 범위에 들어가고, 방문하지 않은 장소이면

#8 : 그래프에서 지나갈 수 있는 공간이면 지금까지 왔던 거리에 +1 더해줌 그리고 새로운 방향과 벽의 여부를 큐에 넣어줌

#9 : 벽을 부수지 않은 상태이고, 방문할 수 없는공간이면 이전까지의 값 (3차원 배열에서 wall=0에서의 값)에 +1을 더해줘서 wall=1인 인덱스의 값으로 옮겨줌(앞으로는 wall=1만 사용) 그리고 새로운 방향과 wall=1을 큐에 넣어줌

(벽을 부수는 순간은 단 한번이고 다음부터는 #8에 걸리게 될것)

#10 : 다 끝나고도 #6에 걸리지 못하면 -1을 리턴

---

14502번 연구소 문제

18405번 경쟁적 전염