검은 방 몇 개를 흰 방으로 바꿔야만 갈 수 있는 경우가 있는데 그럴 경우 되도록 적은 수의 방의 색을 바꾸고 싶음
검은 방을 하나도 흰 방으로 바꾸지 않아도 되는 경우는 0이 답
다익스트라 알고리즘이란?
개념 공부는 아래 유튜브를 참고했다.(나에게 도움을 많이 주신 유튭...) https://youtu.be/acqm9mM1P6o 개념은 이해가 됐는데 코드를 짤 때 가중치를 이해하는 부분이 바로 이해가 안되어서 간략하게 정리를 해보았다. 1. 전체 최종 가중치를 무한으로 초기화 2. 힙에 (0, start)를 최초값으로 넣기 3. 힙이 True일 때 pop 4. 현재의 최종가중치가 간선의 가중치보다 크다면?(만약 헷갈린다면 초기에 초기화한 값인 무한만 대입해서 생각해보기!) 5. 인근 노드에 대해 (내 가중치 + 인근 노드 간선 가중치)와 인근 노드의 최종 가중치를 비교 => 값 업뎃 => 힙에 푸시
🧠 접근 방법
다익스트라 알고리즘으로 최소 경로를 찾아가면서 검은 방의 개수를 탐색
탐색 과정에서 검은 방의 우선순위를 낮게 하여 heap에서 꺼내올 때 가장 나중에 선택되도록 설정
입력
n(한 줄에 들어가는 방의 수, 1<= n <= 50)
~: 0과 1로 이루어진 길이가 n인 수열(0은 검은 방, 1은 흰 방)
출력
흰 방으로 바꿔야 할 최소의 검은 방의 수
👩🏻💻 코드
visited = [[0]*N for _ in range(N)]
나중에 방문 기록을 저장하기 위해 배열을 만들었다.
visited = [[0] * (N+1)] * (N+1)
처음에는 이렇게 코드를 짰는데 배열을 업데이트할 때마다 같은 열에 있는 다른 값도 같이 업데이트가 되길래 약 30분동안 이게 문제라고 생각 못하고 다른 코드만 보다가 팀원 분한테 여쭤보니까 알려주셨다.
위 코드에서 *연산자는 새로운 객체를 생성하지 않고, 기존 객체를 참조하기 때문에 visited[0][0]에 값을 할당하면 visited[1][0], visited[2][0], ...에도 같은 값이 할당된다.
if 0 <= tempx < N and 0 <= tempy < N and visited[tempx][tempy] == 0:
visited[tempx][tempy] = 1
# print(tempx, tempy, "방 확인:", rooms[tempx][tempy])
if rooms[tempx][tempy] == 1:
heapq.heappush(q, (count, tempx, tempy))
else:
heapq.heappush(q, (count + 1, tempx, tempy))
다익스트라 함수에서 지금 방의 인접한 방에 대해 만약 방문하지 않았으면 방문처리 후, 방이 흰 색일 경우에 가중치 그대로 힙에 추가, 방이 검은색일 경우에 가중치에 1을 더해서 힙에 추가해줍니다. 검은색일 경우 1을 추가하는 이유는 이후에 탐색하게 될 방을 pop하게 되는데 그때 가장 후순위에 pop하기 위해서입니다.
📑 전체 코드
# 미로만들기 - 다익스트라
import sys
import heapq
N = int(sys.stdin.readline())
rooms = []
for _ in range(N):
rooms.append(list(map(int, sys.stdin.readline().rstrip())))
mx = [0, 1, 0, -1]
my = [-1, 0, 1, 0]
visited = [[0]*N for _ in range(N)]
def dijkstra(startx, starty):
q = []
heapq.heappush(q, (0, startx, starty))
visited[0][0] = 1
while q:
count, x, y = heapq.heappop(q)
# print("지금 팝:", count, x, y)
if x == (N-1) and y == (N-1):
return count
# visited[x][y] = 1
for i in range(4):
tempx = x + mx[i]
tempy = y + my[i]
if 0 <= tempx < N and 0 <= tempy < N and visited[tempx][tempy] == 0:
## 🚨 tempx, tempy는 힙에 넣었으니까 visited를 네 방향으로 확인하지 않으면 여러번 확인하게 됨
visited[tempx][tempy] = 1
# print(tempx, tempy, "방 확인:", rooms[tempx][tempy])
if rooms[tempx][tempy] == 1:
## 🚨 최소 경로를 찾기 위해서 count를 저장해줌
heapq.heappush(q, (count, tempx, tempy))
else:
## 🚨 최소 경로를 찾을 때 검은 방은 우선 순위에서 뒤로 가야 하므로 count에 1을 더함
heapq.heappush(q, (count + 1, tempx, tempy))
print(dijkstra(0, 0))
