[BOJ] 2206번 벽 부수고 이동하기 / 사용언어 : 파이썬(python)

※ 문제링크

2206번: 벽 부수고 이동하기

해당문제는 BFS를 활용하여 해결할 수 있는 문제였다. BFS구현을 위해 collections의 deque를 활용하였고, 시간 단축과 메모리 절감을 위해 sys를 사용하였다. 처음에는 방문여부만 확인하면서 작성하면 해결할 수 있을 거라 생각하여 코드를 작성했지만, 벽을 부수고 이동했을 경우와 벽을 부수지 않고 이동했을 경우를 나누어 생각해야하는 문제였기에 해결에 실패하였다. 이후에는 변수들을 고려하여 다시 코드를 작성하였고, 자세한 문제풀이와 코드는 아래와 같다.

1. sys함수를 활용하여 입력값을 받고, 반복문을 통해 2차원 배열로 맵을 작성한다. 

2. 방문여부를 확인할 배열을 맵의 형태와 동일하게 작성하고, 벽을 부순 경우와 부수지 않은 경우를 구별하기 위해 입력값을 길이가 3인 리스트로 작성한다. - 벽을 부수지 않은 경우 : [x, y, 0] / 벽을 부순 경우 : [x, y, 1]

3. 부순 벽을 표시하기위해 벽을 부순 경우 맵의 해당 좌표값을 2로 바꾸고, 부순 상태에서 이동하는 경우에는 방문여부를 기록하며, 원래 좌표값이 0이라면 좌표값은 그대로 놔둔 상태로 이동한다.

4. 벽을 부수지 않은 경우 이동시, 좌표값이 0인 경우 방문여부는 상관없이 해당 좌표값을 1로 변경하며 이동한다. 

5. 반복문을 통해 N번째 이동시 갈 수 있는 위치를 기록하고, 마지막 지점이 True면 cnt값을, 마지막 지점에 도달하지 못했는데, queue가 비어있으면 -1을 반환한다.

 

from collections import deque
import sys

N, M = map(int, input().split()) # N: 행의 수(y좌표) / M: 열의 수(x좌표)
# N, M = map(int, sys.stdin.readline().split())
field = []
for _ in range(N):
    field.append(list(map(int, input())))
    # field.append(list(map(int, sys.stdin.readline().rstrip())))
visited = [[False for _ in range(M)] for _ in range(N)] # 전체적인 방문여부 점검

def bfs():
    for _ in range(len(queue)):
        x, y, check = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < M and 0 <= ny < N:
                if check == 0 and field[ny][nx] == 0:
                    queue.append([nx, ny, 0])
                    field[ny][nx] = 2
                    visited[ny][nx] = True
                elif check == 0 and field[ny][nx] == 1:
                    queue.append([nx, ny, 1])
                    field[ny][nx] = 2
                    visited[ny][nx] = True
                elif check == 1 and field[ny][nx] == 0 and visited[ny][nx] == False:
                    queue.append([nx, ny, 1])
                    visited[ny][nx] = True

cnt = 0
t = 0
queue = deque()
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue.append([-1, 0, 0])

while visited[N-1][M-1] == False:
    if len(queue) == 0 and visited[N-1][M-1] == False:
        t += 1
        print(-1)
        break
    bfs()
    # print(cnt, queue, sep = '\n')
    # for i in range(N):
    #     print(field[i])
    # for i in range(N):
    #     print(visited[i])
    # print('')
    cnt += 1
if t != 1:
    print(cnt)

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.