[백준] 1261 알고스팟 (파이썬)

골드 Ⅳ

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

1261번: 알고스팟

 

📄 문제

• 미로는 N*M 크기이며, 총 1*1 크기의 방으로 이루어져 있다.
• 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.
• 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다.
• 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1)이다.
• 벽은 평소에는 이동할 수 없지만, 벽을 부수면 빈 방과 동일한 방으로 변한다.

 

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오

 

 

---

💡 아이디어

1. 다익스트라 알고리즘으로 그래프를 탐색한다.
   • 벽을 부수는 행위에 비용이 1만큼 든다고 생각하고 최소비용을 구하면 된다.
2. heap에 (벽을 부순 개수, 행 위치, 열 위치)를 담는다.
   • 벽을 부순 개수가 적은 방부터 탐색한다.
   • 즉, 벽을 부순 개수가 0인 연결되어 있는 빈 방을 우선적으로 탐색한다.
3. (0,0)을 시작 점으로 두고 동서남북 4방향 탐색을 한다.
4. 빈 방을 만나면, 벽을 부순 개수는 동일하게 현재 위치와 함께  heap에 담아 준다.
5. 벽을 만나면, 벽 부순 개수 + 1을 현재 위치와 함께  heap에 담아 준다. 

 

---

첫 번째 BFS 풀이 코드가 정형화된 다익스트라 알고리즘의 형태로 변형 가능하여,

다익스트라 알고리즘 형태로 두 번째 코드를 한번 더 구현했다.

 

 

🟩 첫 번째 아이디어 (BFS 탐색)

• bfs와 heapq를 활용한다.
• 방문 체크를 하면서 동서남북 4방향을 탐색한다.
• 탐색한 위치 중 벽 부순 개수가 적은 것부터 다시 탐색한다.
• (n-1, m-1)에 도착하면 탐색을 종료한다.

 

✅ 두 번째 아이디어 (다익스트라 알고리즘) - 최종코드 

• 다익스트라 알고리즘으로 그래프를 탐색한다.
• 현재 위치에 저장된 벽 부순 개수가 현재 개수보다 크면 그 위치에서 탐색한다.

 

📝 문제 풀이 (Code)

최종 코드

import sys, heapq
input = sys.stdin.readline

def dijkstra():
    # 벽 부순 개수, 행 위치, 열 위치
    heap = [(0, 0, 0)]
    # 시작점 0
    visited[0][0] = 0

    while heap:
        cnt, i, j = heapq.heappop(heap)

        # 벽 부순 개수가 저장된 값보다 크면 탐색하지 않는다.
        if visited[i][j] < cnt:
            continue

        for k in range(4):
            ni = i + di[k]
            nj = j + dj[k]
            if 0 <= ni < n and 0 <= nj < m:
                # 벽이면 cnt에 1 더 해지고, 빈방이면 그대로 유지된다.
                newCnt = cnt + board[ni][nj]
                # 벽 부순 개수가 저장된 값보다 적으면 갱신한다.
                if newCnt < visited[ni][nj]:
                    visited[ni][nj] = newCnt
                    heapq.heappush(heap, (newCnt, ni, nj))

    return visited[n-1][m-1]


m, n = map(int, input().split())
board = [list(map(int, input().rstrip())) for _ in range(n)]
visited = [[10001]*m for _ in range(n)]
di = [0,1,0,-1]
dj = [1,0,-1,0]

print(dijkstra())

 

처음 코드

heapq를 사용했기 때문에 최종 코드와 효율은 비슷하다.

import sys, heapq
input = sys.stdin.readline

def bfs(i, j):
    # 벽 부순 개수, 행 위치, 열 위치
    heap = [(0, i, j)]
    # 방문 체크
    visited[i][j] = 1

    while heap:
        cnt, i, j = heapq.heappop(heap)

        # (n-1, m-1)에 도착하면 탐색 종료
        if i == n-1 and j == m-1:
            return cnt

        for k in range(4):
            ni = i + di[k]
            nj = j + dj[k]
            if 0 <= ni < n and 0 <= nj < m and not visited[ni][nj]:
                visited[ni][nj] = 1

                if board[ni][nj] == '0':
                    # 빈 방 이면 cnt 개수를 유지한다.
                    heapq.heappush(heap, (cnt, ni, nj))
                else:
                    # 벽이면 부수고 cnt + 1 을 해준다.
                    heapq.heappush(heap, (cnt+1, ni, nj))


m, n = map(int, input().split())
board = [list(input()) for _ in range(n)]
visited = [[0]*m for _ in range(n)]

di = [0,1,0,-1]
dj = [1,0,-1,0]

print(bfs(0, 0))