경쟁적 전염
백준 18405: https://www.acmicpc.net/problem/18405
Abstract
pypy3 환경
- bfs 사용: 348ms
- deque 사용: 336ms
- heapq 사용: 400ms
Edge case
1. 풀이태도
- 한번씩 중간중간 점검해나가면서 풀어야해 (입력은 잘 들어오는지)
- 문제조건 꼼꼼히 읽기 (s는 0부터 시작 등..)
- for 문 안에 list append 있으면 초기화도 생각
2. 범위 설정
- 위치는 1,1부터 시작
- k 이하의 자연수이므로 범위 설정(1, k+1)
Code
1. BFS
- BFS를 사용하되, list에 바이러스의 번호를 따로 넣지 않았으므로,
- virus list를 1부터 k+1까지 만들어서 진행하였음
# 백준 18405
# 경쟁적 전염
# 10:55
# 번호가 낮은 바이러스 부터 증식함, 이미 바이러스가 있다면 들어갈 수 없고
# 바이러스의 위치좌표를 행렬에 저장하는 방식으로 진행해야겠따 (2차원)
# for v in virus
# s초가 지난후에, (x, y)에 있는 바이러스 출력 없으면 0
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
s, x, y = map(int, input().split())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
virus = [[]]*(k+1)
for i in range(1, k+1): # k이하의 '자연수'
tmp = []
for r in range(n):
for c in range(n):
if graph[r][c] == i:
tmp.append([r, c])
virus[i] = tmp
#print(virus)
def bfs():
# 초 개념이 들어가지 (0초 부터 시작)
for _ in range(s):
for i in range(1, k+1):
tmp = []
while virus[i]:
x, y = virus[i].pop()
for d in range(4): # 상하좌우
nx, ny = x+dx[d], y+dy[d]
if nx < 0 or nx >= n or ny < 0 or ny >= n: continue
if graph[nx][ny] == 0:
graph[nx][ny] = i # 바이러스 번호 입력
tmp.append([nx, ny]) # @@ append된 상태로 for문이 한번 더 돌아서 문제 발생
virus[i] = tmp
bfs()
print(graph[x-1][y-1])
# 10000초 뒤에 바이러스 종류는 k
2. deque
- 바이러스의 인덱스와 좌표까지 입력하여 사용하였음.
- for문을 이용해 바이러스 번호 순으로 순차적으로 입력하였기 때문에 정렬하지 않았음
# deque 사용 (정렬 필요가 없기 떄문)
# 10:55 - 11:20
import sys
from collections import deque
input = sys.stdin.readline
n, k = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
s, x, y = map(int, input().split())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
q = deque()
for i in range(1, k+1): # k이하의 '자연수'
for r in range(n):
for c in range(n):
if graph[r][c] == i:
q.append([i, r, c])
def bfs():
# 초 개념이 들어가지 (0초 부터 시작)
for _ in range(s):
tmp = []
while q:
i, x, y = q.popleft()
for d in range(4): # 상하좌우
nx, ny = x+dx[d], y+dy[d]
if nx < 0 or nx >= n or ny < 0 or ny >= n: continue
if graph[nx][ny] == 0:
graph[nx][ny] = i # 바이러스 번호 입력
tmp.append([i, nx, ny]) # @@ append된 상태로 for문이 한번 더 돌아서 문제 발생
for k in range(len(tmp)):
q.append(tmp[k])
bfs()
print(graph[x-1][y-1])
# 10000초 뒤에 바이러스 종류는 k
3. Heapq
- 정렬하지 않아도되었으나, 라이브러리의 작동시간을 확인해보기위해 진행
# heapq 사용 400ms
import sys
import heapq
input = sys.stdin.readline
n, k = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
s, x, y = map(int, input().split())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
q = []
for i in range(1, k+1): # k이하의 '자연수'
for r in range(n):
for c in range(n):
if graph[r][c] == i:
heapq.heappush(q, [i, r, c])
def bfs():
# 초 개념이 들어가지 (0초 부터 시작)
for _ in range(s):
tmp = []
while q:
i, x, y = heapq.heappop(q)
for d in range(4): # 상하좌우
nx, ny = x+dx[d], y+dy[d]
if nx < 0 or nx >= n or ny < 0 or ny >= n: continue
if graph[nx][ny] == 0:
graph[nx][ny] = i # 바이러스 번호 입력
tmp.append([i, nx, ny]) # @@ append된 상태로 for문이 한번 더 돌아서 문제 발생
for k in range(len(tmp)):
heapq.heappush(q, tmp[k])
bfs()
print(graph[x-1][y-1])
# 10000초 뒤에 바이러스 종류는 k
반응형
'코딩테스트' 카테고리의 다른 글
연산자 끼워넣기 Python 정리 및 구현 (백준 14888, 삼성 SW 역량테스트) (0) | 2022.08.30 |
---|---|
괄호변환 Python 정리 및 분석 (프로그래머스, 카카오 기출) (0) | 2022.07.29 |
특정거리의 도시 찾기 Python 정리 및 구현 (백준 18352, 삼성 SW 역량테스트 기출) (0) | 2022.07.28 |
외벽점검 Python 정리 및 구현 (카카오 기출) (0) | 2022.07.28 |
연구소 Python 정리 및 구현 (백준 14502, 삼성 SW 역량테스트 기출) (0) | 2022.07.28 |
댓글