[Python] 백준 2178번 : 미로 탐색 (S1) - DFS&BFS단계별5

#문제

www.acmicpc.net/problem/2178

2178번: 미로 탐색

#풀이 & 학습한 내용

"BFS의 특징은 각 정점을 최단경로로 방문한다는 것입니다. 이 점을 활용해 최단거리를 구해 보는 문제"입니다. 그저 평소의 bfs에서 최단경로를 세는 리스트만 추가해주면 해결되는 문제였습니다. 방문처리를 꼭 해주어 무한루프를 도는 일이 없게 해야 합니다.

 

#소스코드(22번 쨰 줄 주목)

from collections import deque #큐 사용하기 위해 deque import
 
dx = [0,0,1,-1]
dy = [1,-1,0,0] #상하좌우 방향
 
#★ bfs로 최단경로 구할 수 있다
def bfs(miro,sx,sy):
  queue = deque([(sx-1,sy-1)]) #(1,1)에서 시작이니까 인덱스는 (0,0)
  while queue:
    vx,vy = queue.popleft() #큐에서 하나 뽑기
    visited[vx][vy]==True #방문처리
    for i in range(4): #상하좌우 방향
      nx = vx + dx[i]
      ny = vy + dy[i]
      if 0<=nx<N and 0<=ny<M and miro[nx][ny]==1 and not visited[nx][ny]:
        count[nx][ny] = count[vx][vy]+1 #거리 1증가
        queue.append((nx,ny))
        visited[nx][ny]=True #방문처리
 
N,M = map(int,input().split())
 
miro=[list(map(int,list(input()))) for _ in range(N)] #미로 input저장
count=[[0]*M for _ in range(N)] #최단경로 길이 저장할 리스트
count[0][0]=1
visited=[[False]*M for _ in range(N)] #방문여부 저장할 리스트
 
bfs(miro,1,1)
print(count[N-1][M-1])

 

 

github.com/HoYoungChun/Algorithm_PS/blob/master/DFS%26BFS/BOJ_2178.py

HoYoungChun/Algorithm_PS

 

※ 두번째 풀이했을 때의 소스코드

 

문제를 읽고 가중치없는 간선을 가진 최단경로를 구하는 문제임을 파악하고 bfs를 수행해주면 됩니다.

from collections import deque #bfs에서 큐 쓰기위해

dx=[0,0,1,-1]
dy=[1,-1,0,0] #상하좌우방향 for문위해

def bfs(q):
  while q:
    now_pop=q.popleft() #큐에서 하나 뽑기
    now_x = now_pop[0]
    now_y = now_pop[1]
    count = now_pop[2] #이곳까지의 이동횟수

    if (now_x==N-1) and (now_y==M-1): #★bfs니까 찾은순간이 최단경로
      return count

    for i in range(4): #상하좌우방향
      new_x=now_x+dx[i]
      new_y=now_y+dy[i]
      if (0<=new_x<N) and (0<=new_y<M): #미로범위안에 있고
        if maps[new_x][new_y]==1 and not visited[new_x][new_y]: # 이동할 수 있고, 방문한적 없을때
          visited[new_x][new_y]=True #방문처리
          q.append([new_x,new_y,count+1]) #이동횟수 1증가시켜서 큐에 넣기
        

'''최단거리 찾는거니까 bfs하면 된다'''
N,M=map(int,input().split()) #미로의 가로,세로 길이 입력받기

maps=[list(map(int,input()))for _ in range(N)] #미로 입력받기
visited=[[False]*M for _ in range(N)] #방문여부 저장

visited[0][0]=True #시작vertex 방문처리
q=deque([[0,0,1]]) #시작vertex 큐에 넣기([x좌표,y좌표,이곳까지 이동횟수])
print(bfs(q)) #bfs수행해서 최단경로 return된것 print

github.com/HoYoungChun/Algorithm_PS/blob/master/DFS%26BFS/BOJ_2178_2.py

HoYoungChun/Algorithm_PS