Algorithm/BOJ

[BOJ/Python] 2665_미로만들기

O773H 2023. 2. 7. 19:23
728x90

문제 출처:https://www.acmicpc.net/problem/2665

 

2665번: 미로만들기

첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다.

www.acmicpc.net

문제

n×n 바둑판 모양으로 총 n**2개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다.

시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데, 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.

아래 그림은 n=8인 경우의 한 예이다.

위 그림에서는 두 개의 검은 방(예를 들어 (4,4)의 방과 (7,8)의 방)을 흰 방으로 바꾸면, 시작방에서 끝방으로 갈 수 있지만, 어느 검은 방 하나만을 흰 방으로 바꾸어서는 불가능하다. 검은 방에서 흰 방으로 바꾸어야 할 최소의 수를 구하는 프로그램을 작성하시오.

단, 검은 방을 하나도 흰방으로 바꾸지 않아도 되는 경우는 0이 답이다.

입력

첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다.

출력

첫 줄에 흰 방으로 바꾸어야 할 최소의 검은 방의 수를 출력한다.

예제 입력 1

8
11100110
11010010
10011010
11101100
01000111
00110001
11011000
11000111

예제 출력 1

2

 

풀이

 

이 문제는 출발지에서 도착지까지 검은 방을 최소한으로 거쳐 도착했을 때의 지나친 검은 방의 수를 구하는 문제이다.

BFS와 Dijkstra Algorithm을 이용하여 문제를 풀었고, 풀이는 다음과 같다. 

우선, 검은방을 최소한으로 지나야 하므로 하얀 방을 지났을 경우는 1만큼의 거리를 이동하지만, 검은 방을 지났을 경우 BLACK이라는 큰 상수만큼 이동한다고 하겠다. 따라서 어쩔 수 없이 지나쳐야 하는 경우에만 검은 방을 거쳐갈 수 있다.

만약 이와같은 4*4의 방들이 있다고 하자. 출발지는 제일 왼쪽 위인 (0,0)이고 도착지는 제일 오른쪽 아래인 (3,3)이다.

각 영역의 값은 출발지(0,0)로부터의 거리를 나타낸다.

우선 모든 영역에 대하여 출발지와의 거리를 무한대로 초기화한다.

출발지에서 출발지까지의 거리는 0이므로, 0으로 설정하고, 이제 이 방을 기준으로 상하좌우를 탐색한다.

 

우선 탐색한 방이 하얀 방일 경우이다.

  • 하얀 방의 경우, 1만큼 이동한다.
  • 우선 현재 탐색한 방의 경우 출발지로부터의 거리가 무한대라고 설정되어 있다.
  • 이전 방까지의 거리(여기서는 0) + 1(하얀 방이므로 1만큼 이동)과 현재 탐색 중인 방의 거리(현재 무한대)를 비교한다.
  • 비교하였을 때, 이전 방까지의 거리에서 1만큼 움직인 값이 더 작기 때문에 이 값으로 갱신하고, 현재 거리와 좌표를 우선순위 큐에 넣어준다.

  • 우선순위 큐는 최소힙으로 구현되어 있기 때문에, 큐에 들어있는 원소들 중 하나를 뽑는다면 거리의 값이 가장 작은 원소가 나오게 된다.
  • 검은 방을 탐색할 경우에도 마찬가지이다.
  • 이전 방까지의 거리(여기서는 1) + BLACK(큰 상수, 검은 방이므로 큰 상수만큼 이동)과 현재 탐색 중인 방의 거리(현재 무한대)를 비교한다.
  • 마찬가지로 비교하였을 때, 좌항의 값이 더 작기 때문에 이 값으로 갱신하고 우선순위 큐에 넣어준다.
  • 좌항의 값이 더 작다는 의미는 이전 방을 거쳐 이동하였을 때의 거리가 더 짧다는 뜻이다.
  • 하얀 방도 마찬가지로 탐색하여 2의 거리로 갱신하고, 우선수위 큐에 넣어준다.

 

  • 현재 우선순위 큐에 들어있는 원소 중 가장 거리가 작은 값은 1이고, 이 좌표를 기준으로 상하좌우를 탐색한다.
  • 이 좌표를 기준으로 오른쪽 좌표의 경우 1+1과 2를 비교하였을 때, 같기 때문에 추가로 갱신하지 않는다.
  • 아래 좌표의 경우, 1+BLACK과 무한대를 비교하였을 때, 좌항의 값이 작으므로 갱신하고 우선순위 큐에 거리와 좌표를 넣어준다.

  • 현재 우선순위 큐에 들어있는 원소 중 거리가 가장 작은 값은 2이고, 이 좌표를 기준으로 상하좌우를 탐색한다.
  • 이 좌표 기준으로 왼쪽과 위쪽은 2 + 1과 1을 비교하였을 때, 1이 더 작으므로 갱신하지 않는다.
  • 하지만, 오른쪽과 아래쪽은 각각 무한대였으므로 갱신하고 우선순위 큐에 넣어준다.

  • 현재 우선순위 큐에 들어있는 원소 중 거리가 가장 작은 값은 3이고, 이 좌표를 기준으로 상하좌우를 탐색한다.
  • 마찬가지로 왼쪽과 위쪽은 이 좌표를 거쳐서 이동하였을 경우, 더 먼 거리를 가지므로 갱신하지 않는다.
  • 오른쪽과 아래쪽은 무한대였으므로 갱신하고 우선순위 큐에 넣어준다.

  • 현재 우선순위 큐에 들어있는 원소 중 거리가 가장 작은 값은 4이고, 이 좌표를 기준으로 상하좌우를 탐색한다.

  • 이제 우선순위 큐에 들어있는 원소들 중 거리가 가장 값은 1+BLACK이다.
  • 왼쪽 아래에 있는 1+BLACK의 경우 상하좌우를 탐색하더라도 갱신할 좌표가 없다.
  • 이제 오른쪽 위에 있는 1+BLACK을 살펴보면, 이 좌표를 기준으로 오른쪽 좌표가 살펴보면 다음과 같다.
  • (1+BLACK) + 1 과 무한대를 비교한다.
  • 좌항의 값이 작으므로, 해당 좌표의 거리를 갱신하고 우선순위 큐에 넣어준다.

  • 현재 우선순위 큐에 들어있는 원소들 중 거리가 가장 작은 값은 2+BLACK이다. (두 개가 있지만, 어느 쪽이어도 상관없다.)
  • 이 좌표를 기준으로 탐색을 하였을 때, 무한대가 존재하므로 갱신하고 우선순위 큐에 넣어준다.

  • 마찬가지로 3+BLACK을 기준으로 탐색하고, 무한대를 갱신하고 우선순위 큐에 넣어준다.

  • 여기서도 4+BLACK이 3개 있지만, 왼쪽 아래의 존재하는 좌표는 상하좌우를 탐색하더라도 갱신할 부분이 없다.
  • 오른쪽에는 4+BLACK 이 2개 존재하지만, 어떠한 좌표를 먼저 탐색하더라도 상관없다.
  • 무한대가 존재하므로 갱신하고 우선순위 큐에 넣어준다.
  • 이제 마지막으로 우선순위 큐에 존재하는 원소 중 가장 작은 값은 5+BLACK이다.
  • 또한, 현재 큐에서 뽑아낸 원소의 좌표가 우리가 찾는 도착점이므로, 5+BLACK을 반환하고 탐색을 마친다.
  • 그리고 이 값(5+BLACK)을  BLACK으로 나누었을 때의 몫을 구한다. 여기서는 1이고, 이는 곧 검은 방을 한 칸 지나쳤음을 의미한다.
  • Dijkstra Algorithm은 매 상황에서 출발지로부터의 거리의 값이 가장 작은 원소를 선택한다는 점에서 그리디 알고리즘의 성격을 지니고 있다.
  • 현재의 경우는 도착지가 제일 마지막으로 우선순위 큐에 들어갔지만, 그렇지 않을 경우도 있다.
  • 이러한 경우에서 만약 큐에서 원소를 뽑았을 때, 좌표가 도착지라면 현재 상황에서 도착지까지의 가장 짧은 거리가 지금 큐에서 뽑은 거리라고 할 수 있고, 이 값을 반환하고 탐색을 종료한다.

 

코드는 다음과 같다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import sys
import heapq
 
INF = int(1e9)
BLACK = 3000
dx=[-1,0,1,0]
dy=[0,-1,0,1]
 
n = int(sys.stdin.readline())
grid = []
distance = [[INF for _ in range(n)] for _ in range(n)]
 
 
for _ in range(n):
    grid.append(list(sys.stdin.readline().strip()))
 
def dijkstra(grid,distance):
    queue = []
    heapq.heappush(queue,(0,(0,0)))
    distance[0][0] = 0
 
    while queue:
        dist, (x, y) = heapq.heappop(queue)
        if x==n-1 and y==n-1:
            return dist
 
        if dist > distance[x][y]:
            continue
        
        for i in range(4):
            px = x + dx[i]
            py = y + dy[i]
            if 0<=px<n and 0<=py<n:
                if grid[px][py]=='0':
                    if dist+BLACK < distance[px][py]:
                        distance[px][py] = dist+BLACK
                        heapq.heappush(queue,(distance[px][py],(px,py)))
                else:
                    if dist+1 < distance[px][py]:
                        distance[px][py] = dist+1
                        heapq.heappush(queue,(distance[px][py],(px,py)))
 
 
print(dijkstra(grid,distance)//BLACK)
 cs
728x90
저작자표시 비영리 동일조건 (새창열림)