[ 탐색 ] 백준 1261번 알고스팟, 다익스트라

문제 링크

1261번: 알고스팟

 

💡문제 분석 요약

탐색 알고리즘 문제로 최소 개수를 구해야 하는 문제였기 때문에, BFS를 활용하여 문제를 풀이했다. 문제에서 조건을 제한하고 있기 때문에 조건을 따라 문제를 풀이하면 된다.

• 이동할 수 있는 방 == 이동할 수 있는 방향
• 미로 밖으로 이동할 수 없음 
• 1 <=  가로크기(M), 세로크기(N) <= 100  

 

 

💡알고리즘 설계

BFS 알고리즘을 만들기 위해, Queue 자료구조를 사용하며, 벽을 최소한으로 깨야하므로 벽을 깬 횟수를 저장하고, 벽을 최소한으로 깨는 방법을 먼저 찾기 위한 설정을 한다.

• 방을 탐색할 때, 방 정보 == 0(벽이 없음)이라면, applendleft 를 통해 우선적으로 먼저 탐색될 수 있도록 한다.

 

💡코드

from collections import deque

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

graph = []

for i in range(M):
    graph.append(list(map(int, input())))

dist = [[-1] * N for _ in range(M)]  # 벽을 깬 횟수를 저장

dx = [1, 0, -1, 0]  # 행이동
dy = [0, 1, 0, -1]  # 열이동


def bfs(a, b):
    queue = deque()
    queue.append([a, b]) #초기 0,0 값을 큐에 넣는다.
    dist[0][0] = 0  # 첫번째 벽을 깬 횟수는 0으로 초기화

    while queue:
        x, y = queue.popleft() #큐에 있는 값을 왼쪽부터 뺀다.
        for i in range(4):
            nx = x + dx[i]  # 행 이동
            ny = y + dy[i]  # 열 이동

            if nx < 0 or nx >= M or ny < 0 or ny >= N:  # 범위를 벗어나면 아래의 코드를 실행하지 않는다.
                continue

            if dist[nx][ny] == -1:  # 아직 해당 방을 방문하지 않았다면
                # 만약 벽이 없다면
                if graph[nx][ny] == 0:
                    dist[nx][ny] = dist[x][y]  # 전의 벽을 깬 횟수 그대로 전달해준다.
                    queue.appendleft([nx, ny])  # 벽이 없는 곳을 우선적으로 돌도록 큐의 맨 왼쪽에 넣어준다

                # 만약 벽이 있다면
                else:
                    dist[nx][ny] = dist[x][y] + 1  # 전의 벽을 깬 횟수에서 +1 해준다.
                    queue.append([nx, ny])  # 큐의 맨 오른쪽에 추가


bfs(0, 0)
print(dist[M - 1][N - 1])

 

💡시간복잡도

초기화 단계와 BFS 탐색 단계에 의한 시간복잡도는 O(M*N)이다.

• graph와 dist 배열 초기화에서 각각 O(M), O)(M*N)의 시간복잡도를 갖는다.
• BFS 탐색 간, graph의 모든 위치는 한번씩 탐색되며(O(M*N), 각 위치에서의 연산은 O(1)의 시간복잡도를 갖는다.

 

💡 틀린 이유, 다른 풀이

이번 문제는 정해진 시간(20분) 내에 풀이하지 못했다. BFS를 활용한다는 것까지는 좋았으나, "어떻게 최소한으로 이동하는 방법을 탐색할 수 있을까?" 에 대한 답을 내리지 못했다. 

 

다른 풀이를찾아보면서, 내가 문제에 대해 잘못 생각하고 있었다는 사실을 알 수 있었다. 나는 "최적의 길 == 최소한의 이동 + 최소한으로 벽을 부수는 것"으로 생각했다. 분명 최소한의 벽을 부수는 것을 조건이라고 작성하고 시작했는데, 마음이 급했는지 혼자서 엉뚱하게 생각했다.

 

그리고 이 개념이 "다익스트라"라는 것을 알 수 있었다. 내가 알고 있는 다익스트라는 최단 거리를 계산할 때 사용하는 알고리즘인데 이 문제에 적용될 수 있다는 생각을 하지 못했다. 다른 사람의 풀이에서는 최단경로에 사용되는 가중치를 벽을 부수는 비용으로 계산하여 풀이했다.

import heapq

M, N = map(int, input().split())
arr = [list(map(int, input())) for _ in range(N)]
distance = [[1e10] * M for _ in range(N)]

dr = [-1, 0, 1, 0]  # 상 우 하 좌
dc = [0, 1, 0, -1]  # 상 우 하 좌


def dijkstra():
    q = []
    heapq.heappush(q, (0, 0, 0))
    distance[0][0] = 0
    while q:
        cost, r, c = heapq.heappop(q)

        if cost > distance[r][c]:
            continue

        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]

            if nr < 0 or nr >= N or nc < 0 or nc >= M:  # 범위를 벗어나거나 이미 방문했으면 진행x
                continue

            if cost + arr[nr][nc] < distance[nr][nc]:
                distance[nr][nc] = cost + arr[nr][nc]
                heapq.heappush(q, (distance[nr][nc], nr, nc))


dijkstra()
print(distance[N - 1][M - 1])

 

 

💡 느낀점 or 기억할정보

문제를 풀이할 때에는 역시 확실히 차분하게 풀이하는게 중요한 것 같다. 분명하게 명시된 내용은 분명하게 인식하고, 모호한 부분은 해석을 분명히 하여 알고리즘을 설계하는 습관을 갖는 것이 앞으로의 내 숙제가 될 듯하다.

 

과거 다익스트라 알고리즘을 공부하면서, 플로이드 워셜 알고리즘도 함께 들었던 기억이 나는데, 관련해서 해당 알고리즘도 다시금 복습하면 좋을 듯하다.

 

다익스트라 알고리즘은 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 알고리즘이지만, 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 알고리즘이다.