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

🥚문제

---

🥚입력/출력

---

🍳코드

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

n, m = map(int, input().split())
arr = [list(map(int, list(input().strip()))) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 3차원 배열로 표현
# visited[r][c][0] -> 벽을 한 번도 안 뚫었을 때
# visited[r][c][1] -> 벽을 한번이라도 뚫었을 때
visited = [[[0] * 2 for _ in range(m)] for __ in range(n)]

# flag가 1일 때 -> 벽을 한 번이라도 뚫음
# flag가 0일 때 -> 벽을 한 번도 안 뚫음


def bfs(r, c, flag):
    q = deque([])
    q.append((r, c, flag))
    visited[r][c][flag] = 1

    while q:
        r, c, flag = q.popleft()
		
        """
        if flag == 0:
            print("벽을 파괴하지 않은", end=' ')
        else:
            print("벽을 파괴한", end=' ')
        print("(", r, ",", c, ")", "에서 탐색한 결과")
        """

        for i in range(4):
            new_r = r + dx[i]
            new_c = c + dy[i]

            if 0 <= new_r < n and 0 <= new_c < m:
                if arr[new_r][new_c] == 0:
                    if visited[new_r][new_c][flag] == 0:
                        visited[new_r][new_c][flag] = visited[r][c][flag] + 1
                        q.append((new_r, new_c, flag))
                else:
                    if flag == 0:
                        #print("(", new_r, ",", new_c, ") 에서 벽을 파괴")
                        visited[new_r][new_c][1] = visited[r][c][0] + 1
                        q.append((new_r, new_c, 1))

        """
        for row in visited:
            print(row)
        print('='*20)
        """

# bfs 실행
bfs(0, 0, 0)

# 출력
if 0 in visited[n-1][m-1]:
    min_dist = max(visited[n-1][m-1][0], visited[n-1][m-1][1])
else:
    min_dist = min(visited[n-1][m-1][0], visited[n-1][m-1][1])

if min_dist == 0:
    print(-1)
else:
    print(min_dist)

---

🧂아이디어

BFS

• 벽을 부순 것을 어떻게 나타내야 할지가 어려웠던 문제 ⭐⭐⭐⭐⭐

• "벽을 아직 부수지 않은 상태에서 벽을 만나면, 벽을 파괴했다는 표시를 해주고 다시 그 지점에서 bfs 진행" 이라는 첫 번째 아이디어는 시간초과 (반드시 시간 복잡도 생각하고 코드 짜기 ❗)

• visited를 3차원 리스트로 구성하는 방법으로 벽을 부순 것을 표시할 수 있었다
  • visited[r][c][0] : 벽을 한 번도 파괴하지 않은 세계의 (r, c)까지의 이동 거리
  • visited[r][c][1] : 벽을 이미 한 번 파괴한 세계의 (r, c)까지의 이동 거리

• visited 업데이트 방법
  • arr[new_r][new_c]가 0일 때
    • 0인 칸으로는 이동할 수 있으므로, flag에 관계 없이
    • visited[new_r][new_c][flag]= visited[r][c][flag] + 1
  • arr[new_r][new_c]가 1일 때
    • 아직 벽을 부수지 않았다면(flag = 0) 이동 가능
    • visited[new_r][new_c][1] = visited[r][c][0] + 1
    • flag를 1로 업데이트해준다! (벽을 부수지 않은 세계에서 부순 세계로 넘어옴)

(예시)
2 2
01
10
일 때, 각 (r, c)마다 bfs를 한 결과를 출력해보면 🔽

벽을 파괴하지 않은 ( 0 , 0 ) 에서 탐색한 결과
( 1 , 0 ) 에서 벽을 파괴
( 0 , 1 ) 에서 벽을 파괴
[[1, 0], [0, 2]]
[[0, 2], [0, 0]]
====================
벽을 파괴한 ( 1 , 0 ) 에서 탐색한 결과
[[1, 3], [0, 2]]
[[0, 2], [0, 3]]
====================
벽을 파괴한 ( 0 , 1 ) 에서 탐색한 결과
[[1, 3], [0, 2]]
[[0, 2], [0, 3]]
====================
벽을 파괴한 ( 0 , 0 ) 에서 탐색한 결과
[[1, 3], [0, 2]]
[[0, 2], [0, 3]]
====================
벽을 파괴한 ( 1 , 1 ) 에서 탐색한 결과
[[1, 3], [0, 2]]
[[0, 2], [0, 3]]
====================

도움이 되는 게시물: ★☆★☆★ [필독] 벽 부수고 이동하기 FAQ ★☆★☆★