17_경쟁적 전염

2024. 2. 2. 21:28· 알고리즘/이것이 코딩테스트다
728x90
 

18405번: 경쟁적 전염

첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치

www.acmicpc.net

BFS 문제인데 응용해야 하는 문제다.

 

처음에는 전체 바이러스의 시작점의 위치를 큐에 넣고, 각 바이러스를 한번씩 이동시키면 되는 쉬운문제 아닌가?

라는 생각이 들었고, 구현도 시간이 오래 걸리진 않았다.

하지만 하나의 큐에 각 바이러스의 위치를 넣어서 BFS를 구현할 경우, 바이러스를 구분할 수가 없었다.

이걸 보고, 큐를 여러개 만들어야 하나? 라는 생각이 들었는데, 이러면 큐가 너무 많아지는데? 라는 생각이 들어서 넘겨버렸다.

이 때 이걸로 구현했어야 했다...

 

결국 하나의 큐에 모든 바이러스 위치 원소를 넣는 대신, 한 가지 성분을 추가했다.

큐에 (바이러스의 x좌표, 바이러스의 y좌표, 바이러스 번호)를 넣어서, BFS를 돌 때마다 각 바이러스 번호를 해당 칸에 넣어줄 수 있도록 ㅜ구현했다.

 

이러면 될 줄 알고, 구현하다가 심각한 문제에 봉착했다.

그러면, BFS를 돌면서 1초가 지났는지 어떻게 확인을 하지?

라는 문제였다.

전역 변수를 하나 추가해서, 어떻게든 해봤는데 잘 되지 않았다.

결국 최종적으로 결론은 커다란 큐를 하나 만든 후, 매 초가 지날 때마다 도착하는 (바이러스의 x좌표, 바이러스의 y좌표, 바이러스 번호)를 담고 있는 큐를 커다란 큐에 넣는 방식으로 구현했다.

사실 커다란 큐는 리스트로 바꿔도 되지 않을까 싶다.

암튼 이렇게 구현하면 전체 커다란 큐는 항상 하나의 큐를 원소로 가진다.

 

deque([deque([(0, 0, 1), (0, 2, 2), (2, 0, 3)])])

이런식으로.

 

그리고 안에 있는 큐는 해당 s초에서 BFS를 시작할 원소들에 대한 정보를 가지고 있다.

따라서 s초 이후, 그래프의 정보를 위해서는 while문을 s번 돌리면 된다.

 

이런 방식으로 구현을 마쳤는데, 계속 틀린다고 나왔다.

진짜 여기서 30분 넘게 시간을 썼는데,

문제점은 처음에 바이러스 원소에 대한 정보를 입력받을 때, 바이러스 숫자가 낮은 순서로 받아야 하는데,

이걸 간과하고 있었다.

그래서 이 부분 코드를 수정하니 바로 통과했다.

 

 


내 풀이 코드

# 18405번: 경쟁적 전염
from collections import deque

n, k = map(int, input().split())
graph = [] # 전체 시험관
start_list = [] # 초기 바이러스 위치를 저장할 리스트
for i in range(n):
    row = list(map(int, input().split()))
    graph.append(row)
    for j in range(n):
        if graph[i][j] != 0:
            start_list.append((i, j, graph[i][j])) 
            # 일단 초기 바이러스 위치를 리스트에 저장
            # 바이러스 숫자가 낮은 순으로 정렬하려고

start_list.sort(key=lambda x:x[2]) # 바이러스 숫자가 낮은 순으로 정렬
start_list = deque(start_list) # 리스트에서 큐로 변경


s, start_x, start_y = map(int, input().split())

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


# 바이러스 a가 x,y에서 1초 동안 퍼지게 하는 함수
def bfs(x, y, a, temp_queue):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or nx >= n or ny < 0 or ny >= n:
            continue

        # 0이 아니라면 그 칸에는 이미 다른 바이러스가 들어간 것
        if graph[nx][ny] != 0:
            continue
        
        # 0이라면 바이러스가 아직 전염되지 않았으므로 바이러스 i 전염
        if graph[nx][ny] == 0:
            graph[nx][ny] = a
            temp_queue.append((nx, ny, a))

   

# 여러 큐들을 가지고 있는 큐
# 각 큐는 각 초마다 출발해야할 바이러스에 대한 정보를 가지고 있다.
real_queue = deque([start_list])
 
while s > 0:
    queue = real_queue.popleft() # 여러 큐를 가지고 있는 큐에서 해당 초에서 탐색할 큐를 꺼낸다.
    temp_queue = deque([]) # temp_queue는 다음 초에서 감염을 시작할 바이러스의 위치가 저장되어 있는 큐
    while queue:
        now = queue.popleft() # 큐에서 바이러스 위치들을 꺼낸 후
        x, y, virus_num = now
        bfs(x, y, virus_num, temp_queue) # 감염시킨다
    real_queue.append(temp_queue) # temp_queue를 real_queue에 추가한다.
    s -= 1 # 1초 경과
       

print(graph[start_x-1][start_y-1])

 

 


다른 풀이 코드

# 18405번: 경쟁적 전염
from collections import deque

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

graph = [] # 전체 보드 정보를 담는 리스트
data = [] # 바이러스에 대한 정보를 담는 리스트

for i in range(n):
    graph.append(list(map(int, input().split())))
    for j in range(n):
        # 해당 위치에 바이러스가 존재하는 경우
        if graph[i][j] != 0:
            # (바이러스 종류, 위치x, 위치y) 삽입
            data.append((graph[i][j], 0, i, j))

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

target_s, target_x, target_y = map(int, input().split())

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

# BFS 실행
while q:
    virus, s, x, y = q.popleft()
    # 정확히 s초가 지나거나, 큐가 빌 때까지 반복
    if s == target_s:
        break

    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:
                q.append((virus, s+1, nx, ny))

print(graph[target_x - 1][target_y - 1])

 


문제를 좀 더 자세히 읽고, 사소한 것을 놓치지 않도록 해야겠다.

728x90

'알고리즘 > 이것이 코딩테스트다' 카테고리의 다른 글

19_연산자 끼워넣기  (0) 2024.02.06
18_괄호 변환  (0) 2024.02.06
16_연구소  (1) 2024.02.01
15_특정 거리의 도시 찾기  (0) 2024.02.01
14_외벽 점검  (0) 2024.01.30
'알고리즘/이것이 코딩테스트다' 카테고리의 다른 글
  • 19_연산자 끼워넣기
  • 18_괄호 변환
  • 16_연구소
  • 15_특정 거리의 도시 찾기
happenundo
happenundo
happenundo
2023~ 개발블로그
happenundo
전체
오늘
어제
  • 분류 전체보기 (207)
    • TIL (3)
    • 알고리즘 (188)
      • 프로그래머스 (47)
      • 백준 (69)
      • 파이썬 문법 (11)
      • 이것이 코딩테스트다 (46)
      • 알고리즘 노트 (6)
      • SQL (8)
    • Spring (4)
      • Spring 입문 (2)
      • 개인 프로젝트 (1)
      • 인텔리제이 (1)
    • CS (8)
      • DB (2)
      • 네트워크 (1)
      • 그외 (5)
    • ~2022 (1)
    • etc (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 플로이드워셜
  • CS
  • deepcopy
  • 파이썬
  • 백트래킹
  • 이진탐색
  • sql
  • DP
  • BinarySearch
  • 알고리즘
  • 동적프로그래밍
  • 우선순위큐
  • 정렬
  • 이코테
  • BFS
  • 다이나믹프로그래밍
  • 프로그래머스
  • 이것이코딩테스트다
  • 최단거리
  • 완전탐색
  • distinct
  • 구현
  • 큐
  • 다익스트라
  • 스택
  • 백준
  • dfs
  • 괄호변환
  • 재귀
  • 그리디

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
happenundo
17_경쟁적 전염
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.