백준 2178 파이썬

미로 탐색 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

192 MB

167775

74663

47787

43.153%

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입력 1 복사

4 6
101111
101010
101011
111011

예제 출력 1 복사

15

예제 입력 2 복사

4 6
110110
110110
111111
111101

예제 출력 2 복사

9

예제 입력 3 복사

2 25
1011101110111011101110111
1110111011101110111011101

예제 출력 3 복사

38

예제 입력 4 복사

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

예제 출력 4 복사

13

 

 

 

푸는데 꽤 오래걸림.

 

너비우선 탐색 자체가 0,0부터 시작해서 모든 정점을 방문하는 방법이다.

 

너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다.

 

 

일단 이걸 풀기위해서는

 

너비우선탐색 방식이랑

큐 자료구조를 이해해야 함.

 

큐는 아래글참조

https://prodevelop.tistory.com/37

파이썬3 큐 사용법 및 deque 소스코드 원형 c파일

 

너비우선탐색시

 

시작값
101111
101010
101011
111011

중간값
201111
201010
302011
322011

최종 결과값
[3, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 13, 14]
[4, 5, 6, 0, 14, 15]

 

 

소스는 아래참고

https://jokerldg.github.io/algorithm/2021/03/24/maze.html

백준 2178번 미로 탐색 (python 파이썬) - Tech

#콜렉션 선언
from collections import deque

#N,M 입력
N, M = map(int, input().split())

#그래프 선언
graph = []

#그래프 초기화
for _ in range(N):
    graph.append(list(map(int, input())))

#너비우선탐색
def bfs(x, y):
    # 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    # deque 생성
    queue = deque()
    #0,0부터 시작
    queue.append((x, y))

    while queue:
        x, y = queue.popleft()

        # 현재 위치에서 4가지 방향으로 위치 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 위치가 벗어나면 안되기 때문에 조건 추가
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue

            # 벽이므로 진행 불가
            if graph[nx][ny] == 0:
                continue

            # 벽이 아니므로 이동
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))

    # 마지막 값에서 카운트 값을 뽑는다.
    return graph[N-1][M-1]

print(bfs(0, 0))

'''
시작값
101111
101010
101011
111011

중간값
201111
201010
302011
322011

최종 결과값
[3, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 13, 14]
[4, 5, 6, 0, 14, 15]

'''

 

# 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

 

이부분도 상,하,좌,우 할 때

     1

 -1 0  1

     -1

 

이 아니라

 

0,0 기준으로 오른쪽이면 0+1,0 이렇게 됨.

 

그리고

시작값
101111
101010
101011
111011

시작시 

 

0 = {list: 6} [1, 0, 1, 1, 1, 1]
1 = {list: 6} [1, 0, 1, 0, 1, 0]
2 = {list: 6} [1, 0, 1, 0, 1, 1]
3 = {list: 6} [1, 1, 1, 0, 1, 1]

 

0,0 인 1부터 시작해서

 

0 = {list: 6} [1, 0, 1, 1, 1, 1]
1 = {list: 6} [1, 0, 1, 0, 1, 0]
2 = {list: 6} [1, 0, 1, 0, 1, 1]
3 = {list: 6} [1, 1, 1, 0, 1, 1]

 

오른쪽 0은 막혔으니 패스

0 = {list: 6} [1, 0, 1, 1, 1, 1]
1 = {list: 6} [1, 0, 1, 0, 1, 0]
2 = {list: 6} [1, 0, 1, 0, 1, 1]
3 = {list: 6} [1, 1, 1, 0, 1, 1]

 

아래는 1이 있으니 성공하고

0 = {list: 6} [1, 0, 1, 1, 1, 1]
1 = {list: 6} [1+1, 0, 1, 0, 1, 0]
2 = {list: 6} [1, 0, 1, 0, 1, 1]
3 = {list: 6} [1, 1, 1, 0, 1, 1]

 

그후에 +1을 해줌.

그리고 큐에 자리값(1,0)을 추가

 

그리고 다시

0 = {list: 6} [1, 0, 1, 1, 1, 1]
1 = {list: 6} [2, 0, 1, 0, 1, 0]
2 = {list: 6} [1, 0, 1, 0, 1, 1]
3 = {list: 6} [1, 1, 1, 0, 1, 1]

 

상하좌우 비교해서 반복하면 끝