1. 문제
- 백준 18405와 동일한 문제, 문제링크
- N x N 의 시험관
- 바이러스는 1 부터 k번 까지 중 하나
- 바이러스는 1초마다 상하좌우 방향으로 증식
- 번호가 낮은 종류의 바이러스부터 먼저 증식
- 바이러스가 특정칸에 존재하면 그곳에는 다른 바이러스가 들어갈 수 없다.
- S초가 지난 후에 X,Y에 존재하는 바이러스의 종류를 출력하는 프로그램
- S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0 출력
- 시험관의 가장 왼쪽 위는 1,1 이다.
입출력 예시
2. 아이디어
- 동시에 퍼저나가는 것을 구현하고 시간을 측정해야하기에 BFS가 적절할 것으로 생각
- 바이러스를 리스트로 모으고 번호가 낮은 순서로 정렬시킨 후 deque으로 q를 만들고, BFS를 실행한다.
- 동시에 BFS로 퍼지는 시간도 같이 측정한다.
- 퍼지는 시간이 s보다 크면, 아직 퍼지지 않은 것으로 0을 출력하고, 그렇지 않은 경우, 해당 위치 바이러스를 출력한다.
3-1. 틀린 코드
- heapq로 풀면되지 않을까라고 생각 , 틀림
## 입력
n, k = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)] # 좌표와 차이
time = [[-1]*n for _ in range(n)] # 시간 업데이트 할 것
s, x, y = map(int, input().split())
## bfs
dx = [1,-1,0,0]
dy = [0,0,1,-1]
import heapq
def bfs():
q = []
for i in range(n):
for j in range(n):
if maps[i][j] !=0 : # 바이러스면
time[i][j] = 0 # 시간 측정 초기값 입력
heapq.heappush(q, (maps[i][j] , i, j)) # 우선순위 큐에 바이러스 번호 순으로 넣음
while q :
virus, x, y = heapq.heappop(q)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<= nx < n and 0<=ny<n and maps[nx][ny] == 0:
maps[nx][ny] = virus
time[nx][ny] = time[x][y] + 1
heapq.heappush(q, (maps[nx][ny] , nx, ny))
bfs()
if time[x-1][y-1] < s :
print(0)
else :
print(maps[x-1][y-1])3-2. 정답 코드
## 입력
n, k = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)] # 문제 좌표와 차이있음
time = [[-1]*n for _ in range(n)] # 시간 업데이트 할 것
s, x, y = map(int, input().split())
## bfs
dx = [1,-1,0,0]
dy = [0,0,1,-1]
from collections import deque
def bfs():
q = []
for i in range(n):
for j in range(n):
if maps[i][j] !=0 : # 바이러스면
time[i][j] = 0 # 시간 측정 초기값 입력
q.append((maps[i][j] , i, j)) # 큐에 바이러스 번호를 먼저 두고 데이터를 넣는다.
q.sort() # 정렬한다. 번호가 낮은게 먼저 탐색되게
q = deque(q)
while q :
virus, x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<= nx < n and 0<=ny<n and maps[nx][ny] == 0:
maps[nx][ny] = virus
time[nx][ny] = time[x][y] + 1
q.append((maps[nx][ny] , nx, ny))
# 메인
bfs()
if time[x-1][y-1] > s : # 시간내에 도달 못하면
print(0)
else : # 그렇지 않으면
print(maps[x-1][y-1])
4. 배운점
- 처음에 heapq를 생각했다. 그러나 생각해보면, 같은 레벨에서만 바이러스 번호 순으로 나와야 되는데, heaq는 계속해서 바이러스 번호가 낮은 것이 먼저 나오게 되므로 heaq는 적합하지 않다.
- deque으로 q를 만들때, 바이러스 번호 순으로만 넣어줘도, 레벨의 순서안에서 바이러스 번호순으로 퍼저나가게 구현된다.
- deque은 sort로 정렬이 안된다.
참조
- 이것이 취업을 위한 코딩테스트다. with 파이썬
성장하는 데이터 분석가