[알고리즘] 백준 2178 : 미로 탐색 - S1

2023.04.17 풀이

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

n,m=map(int, input().split())
arr=[]

dx, dy= [-1, 1, 0, 0], [0, 0, -1, 1]
for i in range(n):
    arr.append(list(map(int, input().rstrip())))

def bfs(i, j):
    queue=deque()
    queue.append((i, j))
    while queue:
        x,y = queue.popleft()
        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 arr[nx][ny]==1:
                arr[nx][ny]=arr[x][y]+1
                queue.append((nx, ny))
    return arr[n-1][m-1]

print(bfs(0,0))

다른 풀이

N,M=map(int,input().split())
B=[list(map(int,list(input()))) for _ in range(N)]

dy,dx=[0,1,0,-1],[1,0,-1,0]

V=[0]*(N*M)
V[0]=1
q=[(0,0,V[0])]

while q:
    y,x,d=q.pop(0)
    if y==N and x==M:
        break
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if 0<=ny<N and 0<=nx<M and V[ny*M+nx]==0:
            if B[ny][nx]==1:
                q.append((ny,nx,d+1))
                V[ny*M+nx]=d+1
print(V[N*M-1])     

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

n,m=map(int,input().split())
graph=[list(map(int,input().strip())) for _ in range(n)]


dx=[1,0,-1,0]
dy=[0,1,0,-1]

def bfs(x,y):

    q=deque()
    q.append((x,y))

    while q:
        i,j=q.popleft()

        for k in range(4):
            ni=i+dx[k]
            nj=j+dy[k]

            if (0<= ni<n) and (0<=nj<m):
                if(graph[ni][nj]==1):
                    q.append((ni,nj))
                    graph[ni][nj]=graph[i][j]+1
    return graph[-1][-1]

print(bfs(0,0))

check point

• bfs/dfs 판단 기준
  ref1
  ref2

• dfs(깊이우선) : 어떤 경우의 수

  • 현재 나의 위치에서 연결된 브랜치를 모두 방문 후 다음 브랜치로 넘어가는 방법
  • 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법
  • 모든 노드를 방문하고자 할 때 이 방법을 선택. 또는 미로탐색 진행 시 이동할 때 마다 가중치가 붙거나 이동 과정에서 제약이 있을 경우

• bfs(너비우선) : 최단거리, 또는 최소횟수

  • 현재 나의 위치에서 가장 가까운 노드들을 모두 방문
  • 방문하면서 현재위치 pop, 방문할 곳 append, 방문한 곳 check
  • 미로탐색 중 최단 거리를 찾는 문제, 임의의 경로를 찾는 문제에서 사용