우주의 IT 소행성

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

# 좌, 우, 상, 하, 좌상대각, 우상대각, 좌하대각, 우하대각
move_x = [0, 0, -1, 1, -1, -1, 1, 1]
move_y = [-1, 1, 0, 0, -1, 1, -1, 1]


def bfs(i, j):
    graph[i][j] = 0
    queue = deque()
    queue.append((i, j))

    while queue:
        x, y = queue.popleft()
        for i in range(8):
            nx = move_x[i] + x
            ny = move_y[i] + y
            if 0 <= nx < h and 0 <= ny < w and graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))

while True:
    count = 0
    w, h = map(int, input().split())
    if w == h == 0:
        break
    graph = [list(map(int, input().split())) for _ in range(h)]

    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1:
                bfs(i, j)
                count += 1
    print(count)

1. 맵의 모든 부분을 돌면서 육지일 때 너비 우선 탐색을 실행 ( 카운트 + 1 )

2. 너비 우선 탐색시 인접한 모든 섬을 방문하여 0 으로 만듦

3. 섬이 이어지지 않을 경우 다시 1로 돌아감

4. 다시 섬을 구해서 그 섬과 이어진 부분을 전부 0 으로 만듦 ( 카운트 + 1 )

... 위를 반복해서 이어진 섬을 찾는 것

KEY POINT > 이미 탐색된 섬 전체를 0으로 만들어 메인에서 bfs 하지 않게 만들어야 함

from collections import deque

def bfs(s, t):
    queue = deque()
    queue.append((s, t, 0))
    visited = [-1] * (200)

    while queue:
        s, t, count = queue.popleft()
        if s <= t and visited[s] == -1:
            queue.append((s * 2, t + 3, count + 1))
            queue.append((s + 1, t, count + 1))
            if s == t:
                return count


c = int(input())
for i in range(c):
    s, t = map(int, input().split())
    print(bfs(s, t))

bfs를 통해 풀 수 있는 문제.
매 분기마다 A의 발차기를 할지, B의 발차기를 할지
모든 분기를 저장하여 가장 빠른 s == t에 도달한 count를 출력하면 끝.

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

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:
            data.append((graph[i][j], 0, i, j))

data.sort()
queue = deque(data)
t_s, t_x, t_y = map(int, input().split())

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

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

    for i in range(4):
        nx = dx[i] + x
        ny = dy[i] + y
        # 해당 위치로 이동할 수 있는 경우
        if 0 <= nx and nx < n and 0 <= ny and ny < n:
            #아직 방문하지 않았다면 그 위치에 바이러스 넣기
            if graph[nx][ny] == 0:
                graph[nx][ny] = virus
                queue.append((virus, s + 1, nx, ny))
print(graph[t_x - 1][t_y - 1])

BFS로 해결할 수 있는 문제.

맵과 바이러스에 대한 정보를 따로 받는게 핵심이다.

바이러스의 숫자가 낮은 종류부터 먼저 전염을 시켜야 하기 떄문이다.

따라서 맵을 한 줄 한 줄 받을 때 마다 바이러스가 있는지 여부를 체크한 후, 

바이러스가 있다면 해당 바이러스의 위치와 번호를 queue에 입력한다.

오름차순으로 정렬된 queue를 bfs시키면서 채워나가는 방식으로 문제 해결