[백준] 1261번: 알고스팟

🔈 문제

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.
알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.
벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.
만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는 Baekjoon Online Judge에 수록되어 있기 때문에, sudo를 사용할 수 없다.
현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

 

📝입력

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.
(1, 1)과 (N, M)은 항상 뚫려있다.

 

📑출력

첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

 

📚 문제 풀이

오랜만에 데이크스트라 유형의 문제를 풀었다.

본격적인 글쓰기에 앞서 한동안 포스팅이 없었는데 우아한 테크코스 프리코스 과정 중이여서 조금 아니 많이 바빴다..ㅎㅎ 

수고했어 토닥토닥

 

다시 문제로 돌아오면,,

0와 1로 주어진 그래프가 주어지고, (1,1)에서 (n,m)로 갈 때 가장 적게 벽을 부수고 가는 것을 조건으로 할 때 최소 몇 개의 벽을 부숴야지 도착할 수 있는지 찾는 문제였다.

상하좌우 4방향으로 이동을 하고 (1,1) 부터 시작하여 이동할 때 부순 벽의 개수를 저장한 2차원 배열을 생성하고 이때 값은 무한으로 초기화 한다. 이동하면서 부순 벽의 개수를 갱신시켜준다. 이때 데이크스트라 알고리즘을 사용하였다.

 

💻 코드

import sys, heapq
input = sys.stdin.readline
 
m, n = map(int,input().split())
graph = [list(map(int,input().rstrip())) for _ in range(n)]
 
dx = [0,1,-1,0]
dy = [1,0,0,-1]
INF = int(1e9)
distance = [[INF]*(m) for _ in range(n)]
 
 
 
def dijkstra():
    q = []
    heapq.heappush(q, (0, 0, 0)) # cost, x, y
    distance[0][0] = 0
 
    while q:
        dist, x, y = heapq.heappop(q)
        if x == n-1 and y == m-1:
            print(dist)
            return
        if distance[x][y] < dist:
            continue
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
 
            if nx < 0 or ny < 0 or ny >= m or nx >= n:
                continue
            if dist+graph[nx][ny] < distance[nx][ny]:
                distance[nx][ny] = dist + graph[nx][ny]
                heapq.heappush(q, (dist+graph[nx][ny], nx, ny))
 
dijkstra()

 

🍭 시행착오

오랜만에 조금 하드(?)한 문제 풀어서 헤맬줄 알았는데 한번에 성공하여서 나름 뿌듯했다.

🔗 문제링크  알고스팟

1261번: 알고스팟