우주의 IT 소행성

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

from collections import deque
r, c = map(int, input().split())
a = [list(input()) for _ in range(r)]
check = [[False] * c for _ in range(r)]
# 빈 . , 울 # , 늑 v, 양 k
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

def bfs(n1, n2):
    global wolf, sheep

    check[n1][n2] = True
    queue = deque()
    queue.append((n1, n2))

    while queue:
        x, y = queue.popleft()
        if a[x][y] == 'v':
            wolf += 1
        elif a[x][y] == 'k':
            sheep += 1

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < r and 0 <= ny < c and check[nx][ny] == False:
                if a[nx][ny] != '#':
                    queue.append((nx, ny))
                    check[nx][ny] = True


ans = [0, 0] # 양, 늑대
for i in range(r):
    for j in range(c):
        if a[i][j] != '#' and check[i][j] == False:
            sheep, wolf = 0, 0
            bfs(i, j)
            if sheep > wolf:
                ans[0] += sheep
            if wolf >= sheep:
                ans[1] += wolf

print(*ans)

그래프를 bfs로 전체 탐색한 뒤

울타리로 둘러져 있는 곳을 한 구역으로 지정,

해당 구역의 양과 늑대의 총 수를 구한 뒤 비교하여 제출해주면 됨.

from collections import deque
n = int(input())
matrix = [(list(map(int, input().split()))) for _ in range(n)]
queue = deque()
queue.append((0, 0))

while queue:
    x, y = queue.popleft()
    jump_size = matrix[x][y]
    dx = [0, jump_size]
    dy = [jump_size, 0]

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

        if n <= nx or n <= ny:
            continue
        if jump_size == 0:
            continue
        if jump_size == -1:
            print("HaruHaru")
            exit(0)
        queue.append((nx, ny))

print("Hing")

bfs를 통해 이동가능한 모든 경우(우, 하)를 대입시켜 목적지에 도달할 경우

haruharu를, 그렇지 않을 경우 hing을 출력시킨다.

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시키면서 채워나가는 방식으로 문제 해결