17_경쟁적 전염

18405번: 경쟁적 전염

BFS 문제인데 응용해야 하는 문제다.

 

처음에는 전체 바이러스의 시작점의 위치를 큐에 넣고, 각 바이러스를 한번씩 이동시키면 되는 쉬운문제 아닌가?

라는 생각이 들었고, 구현도 시간이 오래 걸리진 않았다.

하지만 하나의 큐에 각 바이러스의 위치를 넣어서 BFS를 구현할 경우, 바이러스를 구분할 수가 없었다.

이걸 보고, 큐를 여러개 만들어야 하나? 라는 생각이 들었는데, 이러면 큐가 너무 많아지는데? 라는 생각이 들어서 넘겨버렸다.

이 때 이걸로 구현했어야 했다...

 

결국 하나의 큐에 모든 바이러스 위치 원소를 넣는 대신, 한 가지 성분을 추가했다.

큐에 (바이러스의 x좌표, 바이러스의 y좌표, 바이러스 번호)를 넣어서, BFS를 돌 때마다 각 바이러스 번호를 해당 칸에 넣어줄 수 있도록 ㅜ구현했다.

 

이러면 될 줄 알고, 구현하다가 심각한 문제에 봉착했다.

그러면, BFS를 돌면서 1초가 지났는지 어떻게 확인을 하지?

라는 문제였다.

전역 변수를 하나 추가해서, 어떻게든 해봤는데 잘 되지 않았다.

결국 최종적으로 결론은 커다란 큐를 하나 만든 후, 매 초가 지날 때마다 도착하는 (바이러스의 x좌표, 바이러스의 y좌표, 바이러스 번호)를 담고 있는 큐를 커다란 큐에 넣는 방식으로 구현했다.

사실 커다란 큐는 리스트로 바꿔도 되지 않을까 싶다.

암튼 이렇게 구현하면 전체 커다란 큐는 항상 하나의 큐를 원소로 가진다.

 

deque([deque([(0, 0, 1), (0, 2, 2), (2, 0, 3)])])

이런식으로.

 

그리고 안에 있는 큐는 해당 s초에서 BFS를 시작할 원소들에 대한 정보를 가지고 있다.

따라서 s초 이후, 그래프의 정보를 위해서는 while문을 s번 돌리면 된다.

 

이런 방식으로 구현을 마쳤는데, 계속 틀린다고 나왔다.

진짜 여기서 30분 넘게 시간을 썼는데,

문제점은 처음에 바이러스 원소에 대한 정보를 입력받을 때, 바이러스 숫자가 낮은 순서로 받아야 하는데,

이걸 간과하고 있었다.

그래서 이 부분 코드를 수정하니 바로 통과했다.

 

 

---

내 풀이 코드

# 18405번: 경쟁적 전염
from collections import deque

n, k = map(int, input().split())
graph = [] # 전체 시험관
start_list = [] # 초기 바이러스 위치를 저장할 리스트
for i in range(n):
    row = list(map(int, input().split()))
    graph.append(row)
    for j in range(n):
        if graph[i][j] != 0:
            start_list.append((i, j, graph[i][j])) 
            # 일단 초기 바이러스 위치를 리스트에 저장
            # 바이러스 숫자가 낮은 순으로 정렬하려고

start_list.sort(key=lambda x:x[2]) # 바이러스 숫자가 낮은 순으로 정렬
start_list = deque(start_list) # 리스트에서 큐로 변경


s, start_x, start_y = map(int, input().split())

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]


# 바이러스 a가 x,y에서 1초 동안 퍼지게 하는 함수
def bfs(x, y, a, temp_queue):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or nx >= n or ny < 0 or ny >= n:
            continue

        # 0이 아니라면 그 칸에는 이미 다른 바이러스가 들어간 것
        if graph[nx][ny] != 0:
            continue
        
        # 0이라면 바이러스가 아직 전염되지 않았으므로 바이러스 i 전염
        if graph[nx][ny] == 0:
            graph[nx][ny] = a
            temp_queue.append((nx, ny, a))

   

# 여러 큐들을 가지고 있는 큐
# 각 큐는 각 초마다 출발해야할 바이러스에 대한 정보를 가지고 있다.
real_queue = deque([start_list])
 
while s > 0:
    queue = real_queue.popleft() # 여러 큐를 가지고 있는 큐에서 해당 초에서 탐색할 큐를 꺼낸다.
    temp_queue = deque([]) # temp_queue는 다음 초에서 감염을 시작할 바이러스의 위치가 저장되어 있는 큐
    while queue:
        now = queue.popleft() # 큐에서 바이러스 위치들을 꺼낸 후
        x, y, virus_num = now
        bfs(x, y, virus_num, temp_queue) # 감염시킨다
    real_queue.append(temp_queue) # temp_queue를 real_queue에 추가한다.
    s -= 1 # 1초 경과
       

print(graph[start_x-1][start_y-1])

 

 

---

다른 풀이 코드

# 18405번: 경쟁적 전염
from collections import deque

n, k = map(int, input().split())

graph = [] # 전체 보드 정보를 담는 리스트
data = [] # 바이러스에 대한 정보를 담는 리스트

for i in range(n):
    graph.append(list(map(int, input().split())))
    for j in range(n):
        # 해당 위치에 바이러스가 존재하는 경우
        if graph[i][j] != 0:
            # (바이러스 종류, 위치x, 위치y) 삽입
            data.append((graph[i][j], 0, i, j))

# 정렬 이후에 큐로 옮기기(낮은 번호의 바이러스가 먼저 증식하므로)
data.sort()
q = deque(data)

target_s, target_x, target_y = map(int, input().split())

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

# BFS 실행
while q:
    virus, s, x, y = q.popleft()
    # 정확히 s초가 지나거나, 큐가 빌 때까지 반복
    if s == target_s:
        break

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 해당 위치로 이동할 수 있는 경우
        if 0 <= nx and nx < n and 0 <= ny and ny < n:
            # 아직 방문하지 않은 위치라면, 그 위치에 바이러스 넣기
            if graph[nx][ny] == 0:
                q.append((virus, s+1, nx, ny))

print(graph[target_x - 1][target_y - 1])

 

---

문제를 좀 더 자세히 읽고, 사소한 것을 놓치지 않도록 해야겠다.