경쟁적 전염 Python 정리 및 구현 (백준 18405, 삼성 SW 역량테스트)

경쟁적 전염

백준 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