우주의 IT 소행성

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

n, m = map(int, input().split())
data = [] # 초기 맵
temp = [[0] * m for _ in range(n)] # 벽을 설치한 맵

for _ in range(n):
    data.append(list(map(int, input().split())))

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

def virus(x, y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and nx < n and ny >= 0 and ny < m:
            if temp[nx][ny] == 0:
                temp[nx][ny] = 2
                virus(nx, ny)

def get_score():
    score = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                score += 1
    return score


def dfs(count):
    global result
    if count == 3:
        for i in range(n):
            for j in range(m):
                temp[i][j] = data[i][j]
        for i in range(n):
            for j in range(m):
                if temp[i][j] == 2:
                    virus(i, j)
        result = max(result, get_score())
        return

    for i in range(n):
        for j in range(m):
            if data[i][j] == 0:
                data[i][j] = 1
                count += 1
                dfs(count)
                data[i][j] = 0
                count -= 1

dfs(0)
print(result)

바이러스를 벽으로 어떻게 가두어야 제일 많은 안전 공간을 확보할 수 있냐의 문제이다.

주어진 벽은 총 3개, 맵의 크기는 8 * 8

총 64C3의 경우의 수를 모두 비교해 제일 많은 공간을 뽑아내면 된다.

비어있는 모든 공간에 3개의 벽을 설치하고, 그때마다의 안전 공간의 크기를 계산한 뒤 비교한다.

이렇게 연산하여 가장 많은 안전 공간을 출력해주면 된다.

BFS/DFS에 브루트포스가 함유된 알고리즘이었다.

from collections import deque
import sys
input = sys.stdin.readline
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n + 1)]

# 모든 도시 최단 거리 초기화
distance = [-1] * (n + 1)
distance[x] = 0  # 출발 도시에서 출발 도시까지 거리는 0

# 모든 도로 정보 입력
for _ in range(m):
    start, end = map(int, input().split())
    graph[start].append(end)

# BFS 실행
queue = deque([x])
while queue:
    now = queue.popleft()
    for next_node in graph[now]:
        if distance[next_node] == -1:
            distance[next_node] = distance[now] + 1
            queue.append(next_node)

# 최단 거리가 K인 도시의 번호 오름차순 출력
check = False
for i in range(1, n + 1):
    if distance[i] == k:
        print(i)
        check = True

# 최단 거리가 K인 도시가 없을 때 -1 출력
if check == False:
    print(-1)

BFS를 사용하여 푼 문제

그래프에서 모든 간선의 비용이 동일할 때에는 너비 우선 탐색으로 손쉽게 해결할 수 있다.

노드의 개수 N의 최대 : 30000

간선의 개수 M의 최대 : 10000

O(N + M)으로 해결해야 하는 문제로, 특정 도시 X를 시작점으로 BFS를 수행해 모든 도시까지의 최단 거리를 계산한 후, 각 최단 거리를 하나씩 확인하며 그 값이 K인 경우에 해당 도시의 번호를 출력한다.

파이썬의 pop() 함수를 잘 사용하여 풀 수 있음(deque 처럼, pop(0), pop())

+ 문제에 reverse 기능이 있는데, 이런 reverse가 나올 떄에는 2번 호출되면 제자리로 돌아온다는 사실을

항상 인지하고 있어야 한다. 매번 reverse를 해주면 그만큼 사용하는 메모리가 많아진다.

그리고 어차피 reverse를 하더라도 주어진 연산은 삭제밖에 없으니, reverse의 토큰 수에 따라서 왼쪽이나 오른쪽 수를 지워주기만 하면 된다.,

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    commands = input()
    n = int(input())
    data = input().rstrip()[1:-1].split(",")
    result = 0
    reverse_count = 0

    if n == 0:
        data = []

    for command in commands:
        if command == 'R':
            reverse_count += 1

        elif command == 'D':
            if len(data) > 0:
                if reverse_count % 2 == 0:
                    data.pop(0)
                else:
                    data.pop()
            else:
                result = -1

    if reverse_count % 2 == 1:
        data.reverse()
    if result == -1:
        print("error")
    else:
        print("[" + ",".join(data) +"]")