파이썬 알고리즘 268번 | [백준 2206번] 벽 부수고 이동하기

268. 벽 부수고 이동하기

1) 어떤 전략(알고리즘)으로 해결?

• bfs

그래프 이론
그래프 탐색
너비 우선 탐색

2) 코딩 설명

<내 풀이>

https://wtg-study.tistory.com/86
https://reliablecho-programming.tistory.com/36

• 방문배열에, 지금 벽을 한번 부수고 방문한 경운지 여부를 넣어주기 위해서 삼차원 배열로 만들어주면 됨
• 방문 배열을 삼차원 배열로 만들어준 것

  visit [][][i]에서 i가 0인 경우는 벽을 부술 수 있는 상태, 1인 경우는 벽을 한번 부 순상태로 나누어 푸는 문제

# 방문
visit = [[[-1]*2 for _ in range(m)] for _ in range(n)]

from collections import deque
import sys
# 내가 도착할 위치
n,m= map(int, sys.stdin.readline().split())
# 상하좌우
dirr = [-1,1,0,0]
dirc = [0,0,-1,1]
# 지도
mapp=[]
for _ in range(n) : 
    mapp.append(list(sys.stdin.readline().strip()))
# 방문
visit = [[[-1]*2 for _ in range(m)] for _ in range(n)]
# 큐
q=deque()
q.append((0,0,0)) # 좌표랑 벽 부숨 여부 
visit[0][0][0]=1 # 안 부숨 상태 = 0 

while q :

    nowr, nowc, broken = q.popleft()

    for i in range(4) : 
        if 0<=nowr+dirr[i]<n and 0<=nowc+dirc[i]<m : # 좌표만 맞는지 검사 

            if mapp[nowr+dirr[i]][nowc+dirc[i]] == '1' and broken==0 : 
                visit[nowr+dirr[i]][nowc+dirc[i]][1] = visit[nowr][nowc][0]+1 
                q.append((nowr+dirr[i], nowc+dirc[i], 1))

            elif mapp[nowr+dirr[i]][nowc+dirc[i]] == '0' and visit[nowr+dirr[i]][nowc+dirc[i]][broken]==-1:
                visit[nowr+dirr[i]][nowc+dirc[i]][broken] = visit[nowr][nowc][broken]+1
                q.append((nowr+dirr[i], nowc+dirc[i], broken))

if (visit[n-1][m-1][0]!=-1 and visit[n-1][m-1][0]>0) and (visit[n-1][m-1][1]!=-1 and visit[n-1][m-1][1]>0): 
    print(min(visit[n-1][m-1][0], visit[n-1][m-1][1]))
elif (visit[n-1][m-1][0]!=-1 and visit[n-1][m-1][0]>0):
    print(visit[n-1][m-1][0])
elif (visit[n-1][m-1][1]!=-1 and visit[n-1][m-1][1]>0):
    print(visit[n-1][m-1][1])
else : 
    print(-1)

< 내 틀렸던 풀이, 문제점>

21% 에 틀린 풀이

from collections import deque
import sys
# 내가 도착할 위치
n,m= map(int, sys.stdin.readline().split())
# 상하좌우
dirr = [-1,1,0,0]
dirc = [0,0,-1,1]
# 지도
mapp=[]
for _ in range(n) : 
    mapp.append(list(sys.stdin.readline().strip()))

# 방문
visit = [ list(-1 for _ in range(m)) for _ in range(n)]
# 큐
q=deque()
q.append((0,0,0))
visit[0][0]=1
while q :
    nowr, nowc, broken = q.popleft()
    for i in range(4) : 

        if 0<=nowr+dirr[i]<n and 0<=nowc+dirc[i]<m \
            and visit[nowr+dirr[i]][nowc+dirc[i]]==-1 :

            if broken==0 and mapp[nowr+dirr[i]][nowc+dirc[i]] == '1': 
                visit[nowr+dirr[i]][nowc+dirc[i]] = visit[nowr][nowc]+1
                q.append((nowr+dirr[i], nowc+dirc[i], 1))

            if mapp[nowr+dirr[i]][nowc+dirc[i]] == '0':
                visit[nowr+dirr[i]][nowc+dirc[i]] = visit[nowr][nowc]+1
                mapp[nowr+dirr[i]][nowc+dirc[i]] = '1'
                q.append((nowr+dirr[i], nowc+dirc[i], broken))

if visit[n-1][m-1]!=-1 : 
    print(visit[n-1][m-1])
else : 
    print(-1)

<반성 점>

<배운 점>