[백준] 18405 경쟁적 전염 - 골드5

[오늘의 문제

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

---

[오늘의 학습 키워드]

• BFS, 구현

---

1. 문제 설명

 

N x N 크기의 시험관이 주어집니다.

 

해당 시험관에는 K개의 바이러스가 존재하는데 바이러스는 순서대로 1번부터 K번까지 존재합니다.

 

바이러스는 낮은 번호부터 빈 칸에 전염을 시작하는데 만약 전염하려는 칸에 이미 바이러스가 존재하는 경우 해당 칸은 전염을 시킬 수 없습니다.

 

바이러스는 전염을 위해 상, 하, 좌, 우 4방향으로 동시에 전염을 시킬 수 있으며 주어진 S초가 경과하였을 때, 주어진 위치에 존재하는 바이러스 번호를 출력하는 프로그램을 작성해야 합니다.

---

[제한사항]

• 시간 제한 1초
• 메모리 제한 256MB
• 1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000
• 0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N
• 둘째 줄부터 N개의 줄에 걸쳐 시험관의 정보가 주어집니다.
• 각 행은 N개의 원소로 구성되며 바이러스가 존재하지 않는 경우 0으로 주어집니다.
• 마지막줄에 시간, 출력할 행, 출력할 열 이 주어집니다.

---

2. 접근 방식

 

전형적인 BFS 구현문제 입니다.

 

쉽게 생각이 가능한 문제인데

 

우선 모든 입력을 받고 초기 바이러스의 위치를 찾아줍니다.

 

바이러스는 낮은 번호부터 전염을 시작해서 높은 번호가 마지막으로 전염을 종료합니다.

 

따라서 처음 바이러스 위치를 찾아서 queue에 넣어준 뒤 해당 queue를 바이러스 번호 순서로 정렬해 줍니다.

 

동시에 queue에 시간 정보도 같이 넣어줍니다.

 

우리가 하고자 하는 것은 S초 후의 시험관 상태이니 시간 정보가 S가 된 경우 더이상 전염을 시키면 안되고 그 상태에서 출력을 실시해 주어야 합니다.

 

즉 순서를 살펴보면

 

1. 모든 바이러스의 위치 정보를 찾아서 queue에 업데이트 하기

- 이때 queue에는 바이러스번호, 행, 열, 시간정보 로 넣어주기

 

2. 입력받은 queue를 바이러스 번호에 따라서 정렬을 실시하기

- 이는 번호가 낮은 종류의 바이러스가 먼저 전염을 시작하기 위함

 

3. BFS 탐색을 실시하며 시험관 정보 업데이트 하기

- 이때 바이러스는 4방향으로 전염을 실시할 수 있고, 이미 바이러스가 전염된 곳은 전염을 시킬 수 없다.

 

4. 시간이 S초가 된 경우 BFS 탐색을 종료하고 해당 위치의 바이러스 정보 출력하기

 

코드로 살펴보겠습니다.

---

3. 코드

import sys
input = sys.stdin.readline
from collections import deque

# 입력
N, K = map(int, input().split())
info = [list(map(int, input().split())) for _ in range(N)]
time, ex, ey = map(int, input().split())    # 시간, 종료 행, 종료 열

# 1. 모든 바이러스 위치 정보 업데이트
queue = deque()
for i in range(N):
    for j in range(N):
        if info[i][j] != 0:
            queue.append((info[i][j], i, j, 0))

# 2. queue 자료 구조를 유지하며 바이러스 번호 순서로 오름차순 정렬
queue = deque(sorted(queue))

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

# 3. 바이러스 전염을 위한 BFS 탐색
while queue:
    virus, x, y, count = queue.popleft()

    # 4. 종료조건
    # 입력받은 시간이 된 경우 더이상 BFS 탐색을 실시하지 않고 종료
    if count == time:
        break

    # 4방향 전염
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]

        if 0 <= nx < N and 0 <= ny < N:
            if info[nx][ny] == 0:
                info[nx][ny] = virus
                queue.append((virus, nx, ny, count + 1))

print(info[ex-1][ey-1])

---

[코드설명]

 

import sys
input = sys.stdin.readline
from collections import deque

# 입력
N, K = map(int, input().split())
info = [list(map(int, input().split())) for _ in range(N)]
time, ex, ey = map(int, input().split())    # 시간, 종료 행, 종료 열

 

입력을 받아줍니다.

 

저는 S 대신 가독성을 위해 time으로 받았고 종료 위치를 출력하기 위한 ex, ey로 받아주었습니다.

---

# 1. 모든 바이러스 위치 정보 업데이트
queue = deque()
for i in range(N):
    for j in range(N):
        if info[i][j] != 0:
            queue.append((info[i][j], i, j, 0))

# 2. queue 자료 구조를 유지하며 바이러스 번호 순서로 오름차순 정렬
queue = deque(sorted(queue))

 

전체 탐색을 실시하며 모든 바이러스 위치 정보와 시간 정보를 업데이트 해줍니다.

 

최초 시간 상태는 0초에서 시작하니 시간 정보를 0으로 넣어주었고, 바이러스 번호를 순서로 오름차순 정렬을 실시할 것이니

바이러스 번호, 행, 열, 시간 순서로 queue에 넣어주었습니다.

 

만약 행,열,바이러스 번호, 시간 등 다른 방식으로 queue에 업데이트한 경우 정렬을 위해 lambda 함수를 사용하면 됩니다.

 

람다 함수는 다음과 같이 사용하면 됩니다.

queue = deque()
for i in range(N):
	for j in range(N):
    	if info[i][j] != 0:
        	queue.append((i, j, info[i][j], 0))

queue = sorted(queue, key = lambda x : x[2])

 

정렬을 실시할 때 정렬 기준을 lambda를 이용해  배열의 3번째 값 index 번호는 2번 값을 기준으로 정렬을 실시하는 방법 입니다.

---

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

# 3. 바이러스 전염을 위한 BFS 탐색
while queue:
    virus, x, y, count = queue.popleft()

    # 4. 종료조건
    # 입력받은 시간이 된 경우 더이상 BFS 탐색을 실시하지 않고 종료
    if count == time:
        break

    # 4방향 전염
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]

        if 0 <= nx < N and 0 <= ny < N:
            if info[nx][ny] == 0:
                info[nx][ny] = virus
                queue.append((virus, nx, ny, count + 1))

print(info[ex-1][ey-1])

 

입력된 queue를 탐색을 실시하며 전염을 시작합니다.

 

전염의 조건은 단순히 다음 위치가 빈 공간인 경우 전염을 실시합니다.

 

정렬을 통해 오름차순 정렬을 이미 완료하였으니 뽑아온 virus값을 다음 위치에 새겨주고 시간 정보를 늘려줍니다.

 

현재 위치를 기준으로 4방향 전염을 실시하기를 반복해서 K번 바이러스 까지 모두 전염을 완료하였다면 queue에는 이제 시간 정보가 1씩 늘어난 바이러스 정보가 담겨 있겠죠

 

이를 토대로 다음 탐색시 시간 정보를 확인하며 다시 바이러스 전염을 실시하는 겁니다.

 

그러다 시간 정보가 입력된 시간 정보와 동일한 경우 BFS를 종료하고 입력받은 위치를 출력합니다.

 

입력받은 위치를 그대로 출력하면 indexError 가 발생하니 1씩 줄여서 출력해 주었습니다.

---

4. 결과

---

[회고]

쉬운 문제 였습니다.

 

처음 시간 초과는 접근 방식을 달리 해보았습니다.

 

queue에서 BFS 탐색을 통해 전염을 실시할 때 시간 정보를 업데이트 하지 않고 전체 탐색, 바이러스 전염을 입력받은 시간 만큼 전체 반복을 실시해 주었습니다.

 

즉 최상단에 입력받은 시간만큼 for 문을 돌리고 그 안에서 전체탐색, BFS를 실시해 주었습니다.

그렇게 하니까 2%에서 시간초과가 발생했습니다.

 

생각해보니 시간은 최대 10000 초 가 주어지고, N의 범위는 최대 200 입니다.

 

이를 계산해보면 4억 번으로 시간 초과가 발생하기 충분했습니다.

 

애초에 전체 탐색을 매 시간마다 계속 실시하니 메모리 복잡도도 많이 잡아먹고 시간 복잡도도 클 수 밖에 없는 코드였습니다.

 

그래서 queue에 정보를 업데이트 할 때 시간 정보도 같이 업데이트 해서 최초 전체 탐색을 1번 실시하고 그 기준으로 전염을 실시할 때, 시간 정보도 같이 queue에 업데이트 하는 방식으로 바꿧고 156ms로 통과할 수 있었습니다.

 

이러면 시간 복잡도가 전체 탐색으로 발생하는 최대 4만 또는 입력받은 K의 수인 1000번 만큼 발생하니 충분히 통과가 되었습니다.

 

이런 구현 문제를 해결할 때는 항상 시간복잡도를 처음에는 고려하지 않고 문제를 먼저 해결해 보고 시간을 줄이는 방식을 적용하는게 맞는 방법 같습니다.