미로 탐색

N * M 리스트가 주어졌을 때 (1,1)에서 (N,M)까지 가는 최단거리를 구하는 문제다.

최단거리를 구하는 문제이기 때문에 BFS로 탐색을 하다가 목적지에 도착하는 순간 저장된 거리를 출력해줘야 한다.

DFS는 STACK을 사용해 구현하는 반면 BFS를 코드로 구현하기 위해서는 선입선출 구조의 큐를 사용한다.

이 문제에서는 지나간 곳은 다시 지나지 않도록 check리스트를 추가로 생성했다. 방문한 곳을 다시 방문한다는 것은 해당 칸 까지 도달하는데 이미 저장되어있는 값과 같거나 혹은 더 오래 걸렸다는 뜻이기 때문이다.

  • check리스트는 우선 0으로 모두 초기화 해주고, 시작지점인 (0,0)만 1로 바꿔준다.
  • 다른 칸으로 이동했을 때 이전 칸의 check리스트 값에서 1을 더해 현재 check리스트 값에 넣어준다.(한칸 씩 이동할 때 마다 이동한 거리가 저장된다.)
  • bfs 큐를 생성해 BFS를 구현한다. 큐에서 원소를 ‘popleft’로 뺄때 마다 해당 칸에서 갈 수 있는 아직 가지 않은 칸을 BFS에 ‘append’해준다.
  • 위의 작업을 도착지에 도착할 때 까지 반복해준다. 최초로 도착지에 도착하게 되면 도착지의 check리스트 값을 출력하고 시스템을 종료한다!(혹은 break를 통해 while문 탈출)


CODE

import sys
from collections import deque

n,m=map(int,input().split())
maze=[]
for _ in range(n):
    tmp=sys.stdin.readline().strip()
    a=[]
    for i in tmp:
        a.append(int(i))
    maze.append(a)
check = list(list(0 for _ in range(m)) for _ in range(n))
check[0][0]=1

bfs=deque([[0,0]]) #너비 탐색을 위한 큐 생성
dx=[-1,0,1,0]
dy=[0,1,0,-1]

while bfs:
    tmp=bfs.popleft()
    if tmp == [n-1,m-1]:
        print(check[-1][-1])
        sys.exit()
    for x,y in zip(dx,dy):
        ax=tmp[0]+x
        by=tmp[1]+y
        if 0<=ax<n and 0<=by<m and check[ax][by]==0 and maze[ax][by]!=0:
            check[ax][by]=check[tmp[0]][tmp[1]]+1
            bfs.append([ax,by])


미로 탐색 - 경로

Crepe

7*7 리스트로 입력이 주어지면 경로의 가지수를 출력하는 문제다.

입력 예시

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

윗 문제에서는 출발지로 부터 도착지 까지 거쳐야 하는 최소의 칸 수를 출력했다면, 이 문제에서는 출발지로 부터 도착지 까지 갈 수 있는 경로의 수를 찾는 문제다. DFS를 사용해서 풀어보자.

  • 먼저 dfs 함수를 만들어 주자.
  • 함수의 입력으로 도착지 좌표가 들어오면 ‘sum’에 +1을 한다.
  • 도착지에 도착하지 못했을 경우 양옆과 위아래 중 아직 거치지 않은 칸을 탐색한다.
  • 아직 거치지 않은, 갈수 있는 칸이 존재할 경우 그 칸을 0 에서 1로 바꾼 후 dfs함수를 실행시킨다.
  • 이렇게 도착지 까지 도달할 수 있는 모든 경우를 구할 수 있다.

CODE

import sys

maze=list(list(map(int,sys.stdin.readline().split())) for _ in range(7))
maze[0][0]=1

dx=[-1,0,1,0]
dy=[0,1,0,-1]
sum=0
def dfs(a,b):
    global sum
    if a==6 and b==6:
        sum+=1
        return
    for x,y in zip(dx,dy):
        if 0<=a+x<7 and 0<=b+y<7 and maze[a+x][b+y]==0:
            maze[a+x][b+y]=1
            dfs(a+x,b+y)
            maze[a+x][b+y]=0

dfs(0,0)
print(sum)


문제를 풀기 전 DFS로 풀어야 할지 BFS로 풀어야 할지 판단을 정확히 하자.


[다시 풀어보기]