백준 BFS/DFS 문제입니다. 알고리즘 숙달을 위한 문제 반복풀이입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

https://www.acmicpc.net/problem/2178

[나의 풀이]

⌛ 소요 시간 28분

N, M = map(int,input().split())

maps = []
for i in range(N):
    data = list(map(int,list(input())))
    maps.append(data)

#우하좌상
dx = [0,1,0,-1]
dy = [1,0,-1,0]

from collections import deque

queue = deque([[0,0]])

while queue:

    x,y = queue.pop()

    for i in range(4):
        newX = x+dx[i]
        newY = y+dy[i]

        if newX>=0 and newX<N and newY>=0 and newY<M:
            if maps[newX][newY]==1:
                queue.appendleft([newX,newY])
                maps[newX][newY] = maps[x][y]+1

print(maps[N-1][M-1])

대표적인 DFS/BFS 활용 최단거리 계산 문제입니다. 이전에 풀었던 문제들과 유사하여 구현하는데 크게 어렵지 않았고 풀이 시간도 많이 줄었습니다.

조금 다르게 풀어본 점은 이전에 알게된 '다른 사람의 풀이'에서 보았던 것처럼 탐색한 경로에 순서대로 +1씩 하면서 목적지에 도달하였을 때 maps의 목적지 좌표 값을 바로 정답으로 출력하는 형태로 구현해보았습니다.🐷🐷🐷

[다른사람의 풀이1]

import sys
from collections import deque
 
n,m = map(int,sys.stdin.readline().split())
array=[]
 
for i in range(n):
    array.append(list(map(int,sys.stdin.readline().strip())))
    
d = [[1,0],[0,1],[-1,0],[0,-1]]
 
def bfs(y,x):
    queue = deque()
    queue.append((y,x))
    while queue:
        y1,x1 = queue.popleft()
        for dx,dy in d:
            if 0<=y1+dy<n and 0<=x1+dx<m:
                if array[y1+dy][x1+dx]==1:
                    array[y1+dy][x1+dx]=array[y1][x1]+1
                    queue.append((y1+dy,x1+dx))
 
 
bfs(0,0)
print(array[n-1][m-1])

다른사람의 풀이들을 여러개 찾아보았지만 이러한 문제는 거의 유사한 풀이방식이었습니다.
저의 풀이와 조금 다른 점은 queue 구조에서 popleft(), append()하여 어느쪽에 append하는지 정도였습니다.🐥🐥🐥

[다른사람의 풀이2]

def finding(a,b): #길을 찾아주자
    visited = [[0]* M for _ in range(N)]
    queue = [[a,b]]
    visited[a][b] = 1 # 방문 처리
    while queue:
        y, x = queue.pop(0)
        for dy, dx in move:
            ny, nx = y + dy, x + dx
            if 0 <= ny < N and 0 <= nx < M and visited[ny][nx] == 0 and maze[ny][nx] != 0:
                visited[ny][nx] = visited[y][x] + 1 # 출발지부터 이동한 거리재기
                queue.append([ny,nx])
    return visited[N-1][M-1] #도착점 도착했을 때 거리

import sys
N, M = map(int, sys.stdin.readline().split())
maze = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
move = [[1,0],[-1,0],[0,1],[0,-1]]
print(finding(0,0)) #출발 지점

위 풀이도 bfs방식을 활용한 유사한 풀이입니다. 조금 다른 점은 vistied list를 활용하여 방문 여부를 판단하는 방식이었습니다.

감사합니다.🐼🐼🐼