백준/ Gold 4 문제 , 백준 파이썬 2665 , 미로만들기 [BFS]

백준/ Gold 4 문제 , 백준 파이썬 2665 , 미로만들기 [BFS]

 

 

풀이 시간

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>

 

 

 

문제 출처

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

2665번: 미로만들기

 

 

풀이

 

 

1. 기본 세팅

 

1. 상하좌우 움직임.

 

2. N 입력받기

 

3. N행의 MAP 리스트 입력

 

 

 

2. BFS, BFS 호출 및 처리

 

우선 visited 를 bfs 함수내에 선언하는데 2차원배열로 선언한다.

 

0번째 원소는 방문유무를 체크해주고

 

1번째 원소는 벽을 부신횟수를 카운트해준다.

 

 

3. 첫방문

 

이제 dq를 돌려가면서 첫방문일때는  dq에 우선 담아주고 방문 표시를 해준다.

 

그 다음 그 위치가 벽인지 길인지 확인하여 벽일경우 벽을 부셔야 하므로 +1 해서 저장해주고

 

길일 경우는 값을 그냥 옮겨만 준다.

 

 

4. 재방문

 

이제 재방문일 경우에는 체크해줘야 할것이 있다.

 

바로, 다음으로 옮길 칸의 벽 부신 횟수가 지금 현재 이동할 칸에 저장되어있는 부신횟수보다 적은지 큰지를 판별해줘야 한다.

 

 

옮길 칸이 벽인데 지금 현재 부신횟수에서 +1 을 한 값보다도 크다면 현재 위치에서 이동하는 것이 더 효율적이므로 +1 한 값으로 바꿔준다.

 

만약, 옮길 칸이 길이라면 지금 현재 부신횟수에서 보다 큰지 보고 현재 위치의 부신횟수보다 더 크다면 현재의 위치에서 이동하는게 더 효율적이므로 현재위치의 값으로 바꿔준다.

 

 

 

이외의 값들은 옮길 위치에 이미 저장되어있는값이 가장 효율적인 방법이므로 dq에 넣어주지 않는다.

 

 

최종적으로 MAP 마지막 1번째 원소에 저장되어있는 값이 최적의 값이므로 그 값만 리턴해줘서 출력시킨다.

 

 

정답

 

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

vertical=[1,-1,0,0]
parallel=[0,0,1,-1]

N=int(input())
MAP=[list(map(int,input().rstrip())) for _ in range(N)]

def bfs(x,y):
    dq=deque()
    dq.append([x,y])
    visited=[[[0,0] for _ in range(N)] for _ in range(N)]
    visited[0][0][0]=1
    while dq:
        X,Y=dq.popleft()
        for i in range(4):
            mx,my=X+vertical[i],Y+parallel[i]
            if 0<=mx<N and 0<=my<N:
                if visited[mx][my][0]==0: # 첫방문
                    dq.append([mx,my])
                    visited[mx][my][0]=1
                    if MAP[mx][my]==0:
                        visited[mx][my][1]=visited[X][Y][1]+1
                    elif MAP[mx][my]==1:
                        visited[mx][my][1]=visited[X][Y][1]
                else:  # 재방문
                    if MAP[mx][my]==0 and visited[mx][my][1]>visited[X][Y][1]:
                        dq.append([mx,my])
                        visited[mx][my][1]=visited[X][Y][1]+1
                    elif MAP[mx][my]==1 and visited[mx][my][1]>visited[X][Y][1]:
                        dq.append([mx,my])
                        visited[mx][my][1]=visited[X][Y][1]
                    
    return visited[N-1][N-1][1]

print(bfs(0,0))