[백준 2206] 벽 부수고 이동하기_ 파이썬(Python) 풀이 방법/테스트 케이스 공유

[문제]

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

2206번: 벽 부수고 이동하기

 

와.. 이 문제는 정말 블로그에 박제할 수 밖에 없는 넘나 인상적인 문제이다. !!!! 

🤦🏻‍♀️ 🤦🏻‍♀️ 🤦🏻‍♀️

먼저, 내가 틀렸던 테스트 케이스를 공유하겠다.

이 테스트 케이스를 만들어내는 것도 정말 오래 걸렸다.  아무리 테케 만들어도 다 맞는걸 우째,, 

오류나는 테스트케이스 찾음 ... 답은 9인데 -1이나옴.
4 6
010011
011001
000010
111110

 

나의 불굴의 의지

 

 

테스트 케이스 찾은 과정 

 

 

 

핵심 아이디어 

 

 

 

[🔥🔥🔥핵심 아이디어🔥🔥🔥]

 

결국 중요한 아이디어는 기존에 최단거리문제는 해당 정점에 방문했으면, 그게 그리디하게 , 그 정점까지의 비용은 최소임을 가정했는데. 지금은 해당 정점까지의 비용이 최소라고 하더라도, 전체로봤을때 최단거리임을 보장하지는 못한다..
왜냐면 아예 도착지에 도착을 못할 수도 있음.!!!! 
다시말하면, 벽을 뚫고 해당정점 최단비용됐는데, 전체로봤을때 거기까지 벽을 안뚫고 오더라도 나중에 뚫는게 더 이득일 수 있음. 그래서 해당 노드에 대해서 이전에 벽을 뚫고 온 비용인지, 벽을 안뚫고 도착한 비용인지 각각 저장해놓아야 한다... !

 

 

[🌼🌼🌼코드🌼🌼🌼]

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)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

# 방문 체크를 2가지 케이스로 나눠서 진행해야함
# [0, 0] : 지나지않은케이스, 벽을 지나온케이스
visited = [[[0, 0] for _ in range(M)] for _ in range(N)]


def bfs():
    # 큐: x, y, 벽을 뚫었는지 여부 (1이면 이제 벽 못뚫음.)
    queue = deque([(0, 0, 0)])
    visited[0][0][0] = 1  # 비용

    while queue:
        x, y, flag = queue.pop()

        # 여기가 이슈임. 무작정 방문했다고 컨티뉴 날려버리면안됨. 두가지 경우로 나눠야함.
        # if visited[x][y] == 1:
        #     continue

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

        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if 0 <= nx < N and 0 <= ny < M:
                # 벽이 뚫여있고, 아직 방문하지 않은 상태
                if graph[nx][ny] == 0 and visited[nx][ny][flag] == 0:
                    queue.appendleft((nx, ny, flag))
                    visited[nx][ny][flag] = visited[x][y][flag] + 1
                # 벽이 막혀있는 상태
                elif graph[nx][ny] == 1 and flag == 0:
                    queue.append((nx, ny, 1))
                    visited[nx][ny][1] = visited[x][y][flag] + 1

    return -1


print(bfs())