[백준 18405] 경쟁적 전염

🍎 [백준 18405] 경쟁적 전염

문제링크

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

18405번: 경쟁적 전염

 

⚾ 코드

from collections import deque

N, K = map(int, input().split())
graph = [[0]*(N+1)]  # 1부터 시작하게 하기 위해서
virus_location = []

for i in range(1, N+1):
    graph.append([0]+list(map(int, input().split())))  # 1부터 시작하게 하기 위해서 0을 붙여줌
    for j in range(1, N+1):
        if graph[i][j] != 0:
            # [virus, x, y, second]
            virus_location.append([graph[i][j], i, j, 0])

S, X, Y = map(int, input().split())

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


def check_range(x, y):
    if x > 0 and y > 0 and x <= N and y <= N:
        return True
    return False


def bfs(q):
    while q:
        virus, x, y, second = q.popleft()
        if second == S:
            # 시간이 되면 종료
            break

        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]

            if check_range(nx, ny) and graph[nx][ny] == 0:
                graph[nx][ny] = virus
                # q에는 이미 virus가 정렬 된 순서로 있기 때문에
                # 따로 sort를 해주지 않아도 virus 크기 순서대로 q에 들어가게 됨.
                q.append([graph[x][y], nx, ny, second+1])


# virus 순으로 정렬
virus_location.sort()

q = deque(virus_location)
bfs(q)
print(graph[X][Y])

 

🔔 해결 과정 & 깨달은 점

- 문제를 읽자마자 BFS 알고리즘을 사용해 풀어야 하는 문제라는 것을 알았다.

- 그러나 접근 방법에 있어 살짝 문제가 있어 해결하기까지 조금 시간이 걸렸다.

- 우선 문제 첫 번째는, 시간으로 주어진 S를 while 문의 조건으로 넣어 반복문으로 돌렸다는 것이다. 1초가 지나고 와서 다시 한 번 q에 append 하는 방법이 잘 못 된 것 같다.

- 두 번째는 q를 처음에 sort 해주었으면, 그 다음부터는 어차피 popleft를 통해 앞에서부터 차례대로 pop하고, 결과를 뒤로 append 하기 때문에 따로 처음만 정렬이 필요하고 그 이후는 정렬이 필요하지 않다. 그러나 그 점을 간과한 나머지 virus_location을 리셋하여 초마다 새로 만들고 계속 sort를하여 반복문을 돌리고 있던 것이다!

다음과 같이 말이다.

def bfs(q):
    while q:

        virus, x, y, second = q.popleft()

        if second == S:
            return True

        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]

            if check_range(nx, ny) and graph[nx][ny] == 0:
                graph[nx][ny] = virus
                virus_location.append([graph[x][y], nx, ny, second+1])
    return False


while virus_location:
    virus_location.sort()
    q = deque(virus_location)
    virus_location = []
    if bfs(q):
        print(graph[X][Y])
        break

- 조금 더 deque의 성질을 잘 생각하면서 풀어야 겠다고 다짐했다.