[코딩테스트] 경쟁적 전염 - 약간 변형 (Python)

---

문제 설명

[기존 문제 - 경쟁적 전염]

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)에 존재하는 바이러스의 종류를 계산해보자.

 

[문제 변형]

5 * 5 의 공간에서 우선순위를 가진 오미크론, 뮤, 델타, 알파 의 4개의 바이러스가 위치해있다.
이 바이러스들은 1분에 상,하,좌,우 한 칸 씩 우선순위가 높은 바이러스부터 증식한다. 또한 증식 과정에서 이미 어떠한 바이러스에 감염됐다면 다른 바이러스에 감염 될 수 없다.

S분이 지난 후에 (X, Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오.

만약 S분이 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 감염 안됨을 출력한다.

 

이 때 2분이 지난 뒤에 (3,2)에 존재하는 바이러스의 종류를 계산해보자.

 

[바이러스 정의]

오미크론 - 1 , 뮤 - 2 , 델타 - 3 , 알파 - 4
(감염력이 강한 바이러스의 우선순위가 높다)

---

로직 설명

 

- 상하좌우로 우선순위 대로 바이러스 증식을 위해 BFS 탐색을 수행한다.

 

graph 변수 : 전체 지역의 정보와 현재 바이러스의 위치가 저장된 그래프 배열
- 5 * 5 그래프에 (1, 1) 위치에 오미크론, (4, 1) 위치에 델타, (1, 3) 위치에 뮤, (5, 5) 위치에 알파가 위치하도록 선언
(없는 위치엔 0)

1	0	3	0	0
0	0	0	0	0
0	0	0	0	0
2	0	0	0	0
0	0	0	0	4

 

data 변수 : 증식해야하는 바이러스 초기 정보
- Format : [우선순위, 증식 시간, 위치 x좌표 , y 좌표]

- 초기값 - 증식시간 0, 바이러스 초기 위치

 

q 변수 : 반복문에서 현재 증식되어야하는 바이러스 순서대로 증식시키기위한 큐, 너비우선탐색 (BFS)
- 초기 : 바이러스의 번호가 낮은 (우선순위가 높은) 순서대로 삽입

-> 너비우선탐색으로 방문하지 않은 위치를 차례대로 방문

 

dx와 dy 배열 : 바이러스가 퍼져나갈 수 있는 방향을 정의한 배열, 한칸씩 상하좌우로 이동

바이러스는 현재 위치에서 x좌표는 dx 만큼, y좌표는 dy 만큼의 증가한 위치에 증식한다.

(예시 : dx가 -1이고, dy가 0인 경우 x좌표는 -1만큼, y좌표는 그대로 유지 되어 바이러스는 왼쪽으로 증식하게 된다.)

 

(dx[i], dy[j]) (-1, 0) : 위쪽 (0, 1) : 오른쪽 (1, 0) : 아래쪽 (0, -1) : 왼쪽

(자세한 소스 설명은 아래의 소스코드에 주석)

---

결과

 

[초기 상태] 

1		3
2
				4

- 초록색 칸이 현재 사람의 위치

 

[1분 뒤]

1	1	3	3
1		3
2
2	2			4
2			4	4

[2분 뒤]

1	1	3	3	3
1	1	3	3
2	2	3		4
2	2	2	4	4
2	2	4	4	4

바이러스 증식이 시작되고 2분 뒤에 사람이 감염된다.

감염된 바이러스는 2번 바이러스로 -뮤- 바이러스에 해당한다.

 

[3분 뒤]

1	1	3	3	3
1	1	3	3	3
2	2	3	3	4
2	2	2	4	4
2	2	4	4	4

3분 뒤면 전체 지역에 바이러스가 증식이 된다.

 

[소스 실행 결과] 

- S분과 (X, Y)를 입력 받아, S분 뒤의 (X, Y) 위치의 바이러스를 출력한다.
- 또한 S분이 지났을 때의 그래프를 출력한다.

---

소스 코드

from collections import deque

virus_dic = {'1':'오미크론', '2':'뮤', '3':'델타', '4':'알파'}
k = len(virus_dic)
n = 5	# 그래프 크기

graph = [[1, 0, 3, 0, 0],
         [0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0],
         [2, 0, 0, 0, 0],
         [0, 0, 0, 0, 4]]  # 전체 지역  정보를 담는 리스트(n*n)

data = [[1, 0, 0, 0],
        [2, 0, 3, 0],
        [3, 0, 0, 2],
        [4, 0, 4, 4]]   # 바이러스에 대한 정보를 담는 리스트 (번호, 시간, 초기위치 좌표 x, y)

# 정렬 이후에 큐로 옯기기 (낮은 번호의 바이러스가 먼저 증식하므로)
data.sort()
q = deque(data)

target_s = int(input('몇분 뒤 : '))
target_x, target_y = map(int, input('사람의 위치 : ').split())      # x, y 입력 : (x,y) 에 존재 하는 바이러스


# 바이러스가 퍼져나갈 수 있는 4가지 위치
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 너비 우선 탐색(BFS) 진행
while q :
    virus, s, x, y = q.popleft()
    # 큐가 빌 때까지 반복
    if s == target_s:	# 지정한 시간 만큼 증식했으면 반복 중단
        break
    
    # 현재 노드에서 주변 4가지 위치를 각각 확인
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 해당 위치로 이동할 수 있는 경우
        if 0 <= nx and nx < n and 0 <= ny and ny < n :
            # 아직 방문하지 않은 위치라면, 그 위치에 바이러스 넣기
            if graph[nx][ny] == 0:
                graph[nx][ny] = virus
                q.append((virus, s + 1, nx, ny))
                
                
# 딕셔너리(맵)에서 바이러스 이름 찾아서 출력
if graph[target_x - 1][target_y - 1] == 0:                      # 해당 위치의 값이 0일 경우 : 감염 안됨
    virus_name = '감염 안됨'
elif virus_dic.get(str(graph[target_x - 1][target_y - 1])) :    # 딕셔너리에서 바이러스 이름 매핑
    virus_name = virus_dic.get(str(graph[target_x - 1][target_y - 1]))
else :                                                          # 바이러스 정보 없을 경우
    virus_name = '정보 없음 (' + str(graph[target_x - 1][target_y - 1]) + ')'

print(target_s, '분 뒤 (%d, %d) 위치의 사람이 감염된 바이러스 : %s' % (target_x, target_y, virus_name))

# 현재 그래프 출력
for i in range(n):
    print(graph[i])

- 이것이 취업을 위한 코딩 테스트다 책 참고, 약간의 변형