BFS : 미로만들기(백준 2665번)

▶ 문제 : https://www.acmicpc.net/problem/2665

2665번: 미로만들기

##### 문제 #####
# n×n 바둑판 모양으로 총 n2개의 방이 있다. 
# 일부분은 검은 방이고 나머지는 모두 흰 방이다. 
# 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 
# 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다.
# 윗줄 맨 왼쪽 방은 시작 방으로서 항상 흰 방이고, 
# 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다.
# 시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데, 
# 아래 그림의 경우에는 시작 방에서 끝 방으로 갈 수가 없다. 
# 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.
# 검은 방에서 흰 방으로 바꾸어야 할 최소의 수를 구하는 프로그램을 작성하시오.
# 단, 검은 방을 하나도 흰방으로 바꾸지 않아도 되는 경우는 0이 답이다.

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

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

 

▶ 접근 방법

힙을 사용해서 바꾸어야 할 검은 방의 수를 최소로 유지하는 것이 중요했다.
힙에 데이터를 넣어 줄 때, 데이터의 입력 순서에 따라 결과가 다르게 나타난다.
예를 들어, 아래 코드에서 [change_count, now_x, now_y] 순으로 데이터를 입력하지 않으면 
의도했던 것과 다른 결과가 나온다.

 

▶ 풀이 코드

import sys, heapq

# 방의 크기와 방의 정보를 입력 값으로 받는다.
room_size = int(sys.stdin.readline().rstrip())
room_info = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(room_size)]
# for room in room_info:
#     print(room)

# 방문 여부 리스트를 만들어준다.
visited = [[0] * room_size for _ in range(room_size)]

# 검은 방에서 흰 방으로 바꿀때마다 change_count를 갱신하고,
# 그 값이 최소 일때의 결과를 나타내는 함수이다.
def BFS():
    heap = []
    # 초기 값으로 변환 횟수 0, 시작점 행 좌표 0, 열 좌표 0을 넣어준다.
    heapq.heappush(heap, [0, 0, 0])
    # 시작점 방문 표시를 해준다.
    visited[0][0] = 1
    
    while heap:
        change_count, now_x, now_y = heapq.heappop(heap)
        
        # 마지막에 도착했을 때 change_count를 출력한다.
        if now_x == room_size - 1 and now_y == room_size - 1:
            print(change_count)
            return
        # 시작점에서 상하좌우를 다 탐색해본다.
        for dir_x, dir_y in (-1, 0), (1, 0), (0, -1), (0, 1):
            new_x, new_y = now_x + dir_x, now_y + dir_y
        
            if 0 <= new_x < room_size and 0 <= new_y < room_size and visited[new_x][new_y] == 0:
                visited[new_x][new_y] = 1
                # 검은 방이었다면
                if room_info[new_x][new_y] == 0:
                    # change_count를 1 늘려준다.
                    heapq.heappush(heap, [change_count + 1, new_x, new_y])
                # 아니라면 그냥 넣어준다.
                else:
                    heapq.heappush(heap, [change_count ,new_x, new_y])

BFS()

 

▶ 관련 링크

2021.11.18 - [알고리즘] - DFS(Depth First Search, 깊이 우선 탐색)이란?

2021.11.18 - [알고리즘] - BFS(Breadth First Search, 너비 우선 검색)이란?

2021.11.19 - [알고리즘] - 그래프(Graph)란?

2021.11.19 - [알고리즘] - BFS : 미로 탐색(백준 2178번)

2021.11.19 - [알고리즘] - BFS : 특정 거리의 도시 찾기(백준 18352번)

2021.11.19 - [알고리즘] - 다익스트라 알고리즘(Dijkstra Algorithm)이란?

2021.11.19 - [알고리즘] - BFS : 최소비용 구하기(백준 1916번)