[코테] 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

문제요약:

2차원 배열이 주어졌을 때, 1,1 에서 n,m까지 가는 최소 이동횟수를 구하시오 다만 한번까지는 벽을 부술수 있습니다.

 

난이도:

골드3

 

소요시간:

40분

 

제출횟수:

2회

 

코딩:

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

n,m = map(int,input().split())
arr= [list(map(int,input().strip())) for _ in range(n)]
visited = [[[0]*m for _ in range(n)],[[0]*m for _ in range(n)]]

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

def bfs():
    q = deque([[0,0,1,0]])
    #y,x,발걸음,벽뿌여부
    while q:
        y,x,c,b = q.popleft()
        if y ==n-1 and x ==m-1:
            return c
        for i in range(4):
            ny = y +dy[i]
            nx = x +dx[i]
            if 0<=ny<n and 0<=nx<m:
                #안나갔고
                if arr[ny][nx]==0 :
                    if not visited[b][ny][nx]:
                        #길이고, 온적 없음
                        q.append([ny,nx,c+1,b])
                        visited[b][ny][nx] = c+1
                elif b:
                    #길이 막혔는데 벽뿌씀
                    continue
                elif not visited[1][ny][nx]:
                    #길이 막혔는데 벽부를 아직 안씀
                    visited[1][ny][nx] = c+1
                    q.append([ny,nx,c+1,1])
    return -1

print(bfs())

BFS를 적용하되, 벽을 부술 수 있는 변수가 있으므로, visited을 두개를 활용 했습니다. bfs이기 때문에 먼저 방문한 것이 무조건 여기까지 온 cost가 더 낮기 때문에, 같은 조건으로 여기 온적이 있다면 통과시키지 않았으며, 벽을 부쉈든 안부쉈든 먼저 끝까지 도착한 경우가 더 cost가 낮기 때문에 도착하면 바로 탈출하게 해 주었습니다. 탈출 하지 못했다면 어떠한 경우에도 도착하지 못한 경우이므로 마지막에  return -1 을 추가해 주었습니다.

추가로 제출 횟수 2번인 이유는 크기 1x1 의 테스트 케이스 를 고려 하지 못해서 입니다. 항상 문제를 풀때는 엣지 케이스를 전부 고려하는생각을 해봐야 할 것 같습니다.