[Python] 2206 - 벽 부수기 (골드4)

1. 문제 설명

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

2206번: 벽 부수고 이동하기

 

---

2. 아이디어

BFS를 활용하면 간단하게 해결할 수 있는 문제. (말은 그렇게 해도 당시에 2시간 정도 걸렸었다.)

벽을 부수는 경우를 고려하는 걸 어떻게 하느냐가 관건인데,

그냥 무식하게 생각해서 "벽을 부신다? 차원을 하나 더 넘자 ㅇㅇ"라고 생각했더니 허무하게 풀렸다.

 

[row][col][벽을 부셨는가?] 라는 내용의 visited를 만들고

벽에 가로막혔는데 아직 [?][?][0]이라면 [?][?][1]로 이동시켜서 다시 bfs를 돌리는 것이다.

최종적으로 마지막 인덱스에 벽을 부순 차원, 부수지 않은 차원 모두 도달하지 못 했다면 -1을 리턴

그 외에는 각각 도달 못한 차원이 있다면 반대 차원의 결과값을 보내고, 둘다 도달했다면 더 작은 값을 리턴한다.

 

나름 재밌는 문제였다.

 

---

3. 코드

import sys
from collections import deque

input = sys.stdin.readline

def bfs(n, m, board):
    vector = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    visited = [[[0]*2 for _ in range(m)] for _ in range(n)]
    queue = deque()
    
    queue.append([0, 0, 0])
    visited[0][0][0] = 1

    while queue:
        y, x, flag = queue.popleft()
        for q, p in vector:
            m_y = y + q
            m_x = x + p
            if 0 <= m_y < n and 0 <= m_x < m:
                if board[m_y][m_x] == 0 and visited[m_y][m_x][flag] == 0:
                    visited[m_y][m_x][flag] = visited[y][x][flag] + 1
                    queue.append([m_y, m_x, flag])
                if board[m_y][m_x] == 1 and flag == 0:
                    visited[m_y][m_x][flag + 1] = visited[y][x][flag] + 1
                    queue.append([m_y, m_x, 1])
    if visited[n-1][m-1][0] == 0 and visited[n-1][m-1][1] == 0:
        return -1
    elif visited[n-1][m-1][0] == 0:
        return visited[n-1][m-1][1]
    elif visited[n-1][m-1][1] == 0:
        return visited[n-1][m-1][0]
    else:
        return min(visited[n-1][m-1][0], visited[n-1][m-1][1])

def solution():
    n, m = map(int, input().split())
    board = [list(map(int, input().rstrip())) for _ in range(n)]

    print(bfs(n, m, board))

solution()