[백준] 2206번 벽 부수고 이동하기 _ Python

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

 

---

 

1. Preview

시간 복잡도: O(2N^2)

 

공간 복잡도: O(2N^2)

 

참고 : https://hongcoding.tistory.com/18 (최적화)

 

유형: bfs

 

 

---

 

2. 초기 접근 방법

1개의 벽을 부술 수 있는 "item"이 있다고 생각하자.

 

기존의 visited 배열에서는 item 사용 유무를 판단할 수 없으므로

visited[i][j] → visited[i][j][2] 로 설정한다.

 

 

 

bfs 탐색을 하는데 있어 3가지 경우가 있다.

 

1) 벽

   - 벽 미방문 & item 미사용

 

2) 길

   - 길 미방문 & item 미사용

   - 길 미방문 & item 사용

 

for k in range(4):
    nx = x + dx[k]
    ny = y + dy[k]
    if 0 <= nx < N and 0 <= ny < M:
        ex = board[nx][ny]
        # (nx, ny) 벽
        if  ex == "1":
            # 지금까지 item 미사용 & 해당 칸 벽 미방문
            if not item and not visited[nx][ny][1]:
                visited[nx][ny][1] = visited[x][y][0] + 1 # 해당 칸 벽 뚫는다고 체크
                q.append((nx, ny, True))

        # (nx, ny) 길
        else:
            # 지금까지 item 사용 & 해당 칸 길 미방문
                # 길인데 item 사용한 경우에는, visited[nx][ny][1] 방문 여부를 체크해줘야
            if item and not visited[nx][ny][1]:
                q.append((nx, ny, True))
                visited[nx][ny][1] = visited[x][y][1] + 1

            # 지금까지 item 미사용 & 해당 칸 벽 미방문
                # 길인데 item 미사용한 경우에는, visited[nx][ny][0] 방문 여부를 체크해줘야
            elif not item and not visited[nx][ny][0]:
                q.append((nx, ny, False))
                visited[nx][ny][0] = visited[x][y][0] + 1

 

 

---

 

3. 생각

위 로직을 다음과 같이 최적화 할 수 있다.

 

1) 벽

   - item 미사용 (1번만 사용하므로, 벽 방문은 체크하지 않아도 된다.)

 

2) 길

   - item 사용 유무를 고려한 방문 여부 파악

 

for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0 <= nx < N and 0 <= ny < M:
        # (nx, ny) 벽 & 아이템을 사용하지 않는 경우
        if board[nx][ny] == "1" and not item:
                visited[nx][ny][1] = visited[x][y][0] + 1 # 해당 칸 벽 뚫는다고 체크
                q.append((nx, ny, 1))

        # (nx, ny) 길 & 아직 한 번도 방문하지 않은 곳
        elif board[nx][ny] == "0" and visited[nx][ny][item] == 0:
            visited[nx][ny][item] = visited[x][y][item] + 1
            q.append((nx, ny, item))

 

 

---

 

4. 코드

 

1) 초기 코드

import sys
from collections import deque
input = sys.stdin.readline

def bfs():
    q = deque()
    q.append((0, 0, False))
    visited[0][0][0] = 1
    visited[0][0][1] = 1

    while q:
        x, y, item = q.popleft()

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < N and 0 <= ny < M:
                ex = board[nx][ny]
                # (nx, ny) 벽
                if  ex == "1":
                    # 지금까지 item 미사용 & 해당 칸 벽 미방문
                    if not item and not visited[nx][ny][1]:
                        visited[nx][ny][1] = visited[x][y][0] + 1 # 해당 칸 벽 뚫는다고 체크
                        q.append((nx, ny, True))

                # (nx, ny) 길
                else:
                    # 지금까지 item 사용 & 해당 칸 길 미방문
                        # 길인데 item 사용한 경우에는, visited[nx][ny][1] 방문 여부를 체크해줘야
                    if item and not visited[nx][ny][1]:
                        q.append((nx, ny, True))
                        visited[nx][ny][1] = visited[x][y][1] + 1

                    # 지금까지 item 미사용 & 해당 칸 벽 미방문
                        # 길인데 item 미사용한 경우에는, visited[nx][ny][0] 방문 여부를 체크해줘야
                    elif not item and not visited[nx][ny][0]:
                        q.append((nx, ny, False))
                        visited[nx][ny][0] = visited[x][y][0] + 1



N, M = map(int, input().split())
board = [input() for _ in range(N)]

visited = [[[0 for _ in range(2)] for _ in range(M)]  for _ in range(N)]
visited[0][0][0] = 1

dx = [-1,0,0,1]
dy = [0,-1,1,0]

bfs()

# 아이템 사용, 미사용
itemNo = visited[N - 1][M - 1][0]
itemYes = visited[N - 1][M - 1][1]

# 탈출 불가능
if itemNo == 0 and itemYes == 0:
    print(-1)
# 아이템을 써도, 안써도 탈출 가능할 때
elif itemNo and itemYes:
    print(min(itemNo, itemYes))
# 둘 다 값이 있을 때
else:
    print(max(itemNo, itemYes))

 

 

 

2) 최적화 코드

import sys
from collections import deque
input = sys.stdin.readline

def bfs():
    q = deque()
    q.append((0, 0, False))

    while q:
        x, y, item = q.popleft()

        if x == N-1 and y == M-1:
            return visited[x][y][item]

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                # (nx, ny) 벽 & 아이템을 사용하지 않는 경우
                if board[nx][ny] == "1" and not item:
                        visited[nx][ny][1] = visited[x][y][0] + 1 # 해당 칸 벽 뚫는다고 체크
                        q.append((nx, ny, 1))

                # (nx, ny) 길 & 아직 한 번도 방문하지 않은 곳
                elif board[nx][ny] == "0" and visited[nx][ny][item] == 0:
                    visited[nx][ny][item] = visited[x][y][item] + 1
                    q.append((nx, ny, item))
    return -1



N, M = map(int, input().split())
board = [input() for _ in range(N)]

visited = [[[0 for _ in range(2)] for _ in range(M)]  for _ in range(N)]
visited[0][0][0] = 1

dx = [-1,0,0,1]
dy = [0,-1,1,0]

print(bfs())