백준 2178번 : 미로 탐색(python)

문제

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

코드

dfs로 푼 코드(맞는지 모름...시간초과남)

import sys
def dfs(x,y,cnt):
    global n,m,min
    if(x==m-1 and y==n-1):
        cnt+=1
        if(min>cnt):
            min=cnt
        return False
    if(x<0 or y<0 or x>=m or y>=n):
        return False
    if(graph[y][x]==1):
        cnt+=1
        graph[y][x]=0
        dfs(x+1,y,cnt)
        dfs(x-1,y,cnt)
        dfs(x,y+1,cnt)
        dfs(x,y-1,cnt)
        graph[y][x]=1       
        return True
    return False
if __name__=="__main__":
    n,m=map(int,sys.stdin.readline().split())
    cnt=0
    min=10001
    graph=[]
    for i in range(n):
        result=list(map(int,sys.stdin.readline().rstrip()))
        graph.append(result)
        
    dfs(0,0,cnt)
    print(min)

bfs로 푼코드

import sys
from collections import deque
def bfs(x,y,rx,ry):
    queue=deque()
    visit=[]
    dx=[-1,0,1,0]
    dy=[0,-1,0,1]
    queue.append((x,y))   
    while(queue):
        x,y=queue.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if(nx>=rx or ny>=ry or nx<0 or ny<0):
                continue
            if(graph[ny][nx]==0):
                continue
            if(graph[ny][nx]==1):
                graph[ny][nx]=graph[y][x]+1
                queue.append((nx,ny))
    return graph[ry-1][rx-1]

            
if __name__=="__main__":
    y,x=map(int,sys.stdin.readline().split())
    graph=[]
    for i in range(y):
        result=list(map(int,sys.stdin.readline().rstrip()))
        graph.append(result)
    print(bfs(0,0,x,y))

코드설명

dfs의 방식

1. 미로를 이중리스트로 입력받는다.

2. 최소값의 초기값을 절대 최소값이 될수없는 값으로 설정해준다.

3. x,y값이 음수나 도착값보다 크면 리턴해준다.

4. 값이 1(길)이면 1을 0으로 변경(지나온 자리임을 표시)해주고, 상하좌우의 모든 좌표를 넣어 재귀함수를 돌려준다.

5. 재귀함수를 계속 돌려, 도착좌표에 도착했을때 최소값(min)보다 작다면 min을 변경해주는것을 반복하면서 '모든' 경우의 수를 돌려 min이 가장 작은 값이 만들어졌다면 min을 리턴하여 출력 

bfs의 방식

1. 미로를 이중리스트로 입력받는다.

2-1. 값이 0(벽)이거나, x,y값이 음수나 도착값보다 크면 리턴해준다.

2-2. 값이 1(길)이면 길 이전의 값에 1을 더해 값을 최신화 시켜준다.(bfs이므로 한 위치에 다른 경로로 온 경우의 수가 겹칠수도 있지만 최신화를 시켜줌으로써 이미 최단거리의 경로가 이미 값을 1에서 다른값으로 변경해놓았기때문에 이것을 방지할수 있다.)

3. 도착좌표에 도달하면 도착좌표의 값을 반환하여 출력해준다.

 

느낀점 및 배운점

처음에 dfs로 문제를 풀려 시도하였을때 '시간초과'가 생겨 반례가 있나 싶어 반례를 찾아 넣었는데 내가 찾은 반례에서는 모두 맞다고 나왔다. 뭐가 문제인가를 생각하였는데, dfs는 운이 아주좋으면 바로 원하는 값을 찾을수있지만 운이 나쁘면 모든 경우의 수를 돌려야한다는 단점이 있어 시간이 오래걸린다는 점을 생각하지 못하고 있었다.

그래서 bfs를 사용하여 문제를 풀었고, 가능하면 bfs를 이용하여 최단거리 문제를 푸는것이 효율적이라는 것을 알수있었다.