[PYTHON] 백준 18405 - 경쟁적 전염

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

성능 요약

메모리: 118172 KB, 시간: 272 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현

문제 설명

NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.

시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.

시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과 열의 위치를 의미하며, 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당한다.

예를 들어 다음과 같이 3x3 크기의 시험관이 있다고 하자. 서로 다른 1번, 2번, 3번 바이러스가 각각 (1,1), (1,3), (3,1)에 위치해 있다. 이 때 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류를 계산해보자.

1초가 지난 후에 시험관의 상태는 다음과 같다.

2초가 지난 후에 시험관의 상태는 다음과 같다.

결과적으로 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류는 3번 바이러스다. 따라서 3을 출력하면 정답이다.

입력

첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분되어 주어진다. 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어진다. 또한 모든 바이러스의 번호는 K이하의 자연수로만 주어진다. N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)

출력

S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력한다. 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.

---

아이디어, 문제풀이

• 큐를 활용해서 풀이 해야만 번호 순서대로 실행이 가능하기에, bfs를 선택해 문제풀이를 진행하는게 좋을것 같다. (dfs론 안풀어봤다.)
• 이전 어둠의 군주 이민혁 문제(백준 탈출 문제) 에서 공부했던, 순차적으로 넣어주는 방법을 생각해 내서 문제에 적용할 수 있다면 어렵지 않게 풀 수 있다.

---

TROUBLE SHOOTING

• 저어어어엉말 아쉬웠던 문제. 코딩테스트에서 마지막 문제로 출제됐는데, 진짜 마지막 출력값 다듬는 과정만 남겨두고 다푼 문제다. 심지어 답이 바로 나와서 더 슬펐던 문제.

• 일단, 나는 인덱스 저장, 임의의 값에 저장후 리턴, 이런 방식은 앞으로 절대 사용하지 않을것 같다. 이 문제에서 처럼, 시간초를 time = [[0] * n for _ in range(n)] 에 담아 출력값을 다듬는 과정에서 연산하는게 훨씬 더 직관적이고 편한것 같다.

• 앞선 아이디어에서 말한 과정은 다음 코드를 통해 자세히 설명할 수 있다.

      for i in range(1, k+1):
          for a in range(n):
              for b in range(n):
                  if graph[a][b] == i:
                      que.append((a,b))

  결국, 여태까지 받아오는 입력값들을, 문제에서 주어진 순서를 통해 집어넣어 준다는건데, 해석하면 바이러스 숫자가 graph에 입력되어 있다면 queue에 append를 해줄것이고, 그 과정을 1부터 k+1까지 반복하겠다는 의미다. 이해하면 쉽다!
  

• 아까 앞서 말했던 배열로 받아오게되면, 출력값을 유연하게 조작할 수 있고, 쉽게 해석해서 빠르게 답을 찾아낼 수 있다. 실제로 내 배열에 입력받아올때, 출력값의 위치가 내가 원했던 위치랑 달랐는데, 배열을 조금 조작해서 쉽게 찾아낼 수 있었다.

  # print(result)
  # print(time)
  
  #함수는 0부터 사직하기 떄문에!
  ans_x = x-1
  ans_y = y-1
  if time[ans_x][ans_y] <= s:
      print(result[ans_x][ans_y])

---

코드

#https://www.acmicpc.net/problem/18405
#경쟁적 전염
#18405

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

n, k = map(int, input().split())

graph = []
for _ in range(n):
    a = list(map(int,input().split()))
    graph.append(a)

# print(graph)

s, x, y = map(int, input().split())

visit = [[0] * n for _ in range(n)]

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

time = [[0] * n for _ in range(n)]

def bfs(graph):

    que = deque()
    # que.append((a,b))

    for i in range(1, k+1):
        for a in range(n):
            for b in range(n):
                if graph[a][b] == i:
                    que.append((a,b))
                    # que.append((a,b,0))
    while que:
        x, y = que.popleft()
        # x, y, second= que.popleft()
        
        # if second == s:
        #     break
        visit[x][y] = 1

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

            if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == 0:
                if graph[nx][ny] == 0:
                    graph[nx][ny] = graph[x][y]
                    time[nx][ny] = time[x][y] + 1
                    que.append((nx, ny))
                    # que.append((nx, ny, second + 1))

    return graph

result = bfs(graph)
# print(result)
# print(time)

#함수는 0부터 사직하기 떄문에!
ans_x = x-1
ans_y = y-1
if time[ans_x][ans_y] <= s:
    print(result[ans_x][ans_y])

else:
    print(0)