[Today I Learned 08] 1. 백준 (#1697, #18405, #1939)

문제는 #1697, #18405, #1939이다. 이번에는 3문제중에서 2문제 맞추는 것을 목표로 삼았다. 다행히 목표한대로 2문제를 맞췄다. 저번주에는 1문제를 맞춰서 공부 방법을 1문제를 너무 오래 붙잡지 않고 30분 생각하고 15분정도 코드를 짜보고 안되면 답을 보면서 공부하는 방식으로 진행했다. 생각보다 효율이 좋았던 것 같다. 이제 차례대로 푼 문제를 리뷰해보자!!

1. 숨바꼭질(#1697)

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

이번 문제는 BFS를 이용해서 어렵지 않게 구현할 수 있었다.

from sys import stdin
from collections import deque

# 최대 값은 10만으로 주어짐
MAX = 10**5
input = stdin.readline

# N: 현재 점, K: 동생점
N, K = map(int, input().split())

# bfs로 경우의 수 다 돌기
def bfs():
    # 깊이 변수
    visited = [0] * (MAX + 1)
    queue = deque([N])

    while queue:
        # num: 현재 점, depth: 깊이
        num = queue.popleft()

        # 현재 점과 동생 점이 같이지면 깊이 출력
        if num == K:
            print(visited[num])
            break

        # 현재 점에서 -1, +1, *2 다 해보기
        for x in [num-1, num+1, num*2]:
            if 0 <= x <= MAX and visited[x] == 0:
                visited[x] = visited[num] + 1
                queue.append(x)
bfs()

2. 경쟁적 전염(#18405)

문제

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

1초가 지난 후에 시험관의 상태는 다음과 같다.

2초가 지난 후에 시험관의 상태는 다음과 같다.

결과적으로 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류는 3번 바이러스다. 따라서 3을 출력하면 정답이다.

입력

첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분되어 주어진다. 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어진다. 또한 모든 바이러스의 번호는 K이하의 자연수로만 주어진다. N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)

출력

S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력한다. 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.

이 문제의 핵심은 시간초가 되었을 때 더 이상 BFS가 돌지 않게 하는 것과 오름차순으로 바이러스가 퍼져나간다는 것이다.
1. 미로찾기와 같은 느낌으로 현재 좌표를 방문처리하고 상하좌우를 돌면서 채워나갈 수 있는 부분들을 채운다.
2. BFS를 돌때 현재 큐에 들어있는 개수 만큼만 돌고 시간을 1 올려준다.

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

# 행과 열
row, col = map(int, input().split())
# 방향
direction = ((-1, 0), (1, 0), (0, -1), (0, 1))
# 큐배열
queue = []
# 방문 체크
visited = [[False] * col for _ in range(row)]
# 바이러스 배열
arr = [[0]*col for _ in range(row)]
# 배열 초기화
for x in range(row):
    temp = list(map(int, input().split()))
    for y, data in enumerate(temp):
        if data != 0:
            arr[x][y] = data
            queue.append([data, x, y])
# 초, x, y 좌표
S, X, Y = map(int, input().split())

cnt = 0
while True:
    if cnt == S:
        break
    queue = deque(sorted(queue))
    for _ in range(len(queue)):
        data, x, y = queue.popleft()
        visited[x][y] = True
        for dx, dy in direction:
            new_x = x + dx
            new_y = y + dy
            if 0 > new_x or new_x >= row or 0 > new_y or new_y >= row:
                continue
            if not visited[new_x][new_y] and arr[new_x][new_y] == 0:
                arr[new_x][new_y] = data
                queue.append([data, new_x, new_y])
    cnt += 1

print(arr[X-1][Y-1])

3. 중량제한(#1939)

문제

N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.
영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.
한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력

첫째 줄에 답을 출력한다.

이번 문제는 경로의 값을 구하는 것을 보고 다익스트라로 접근했다. 하지만 다익스트라고 코드를 작성하다 보니깐 누적 합에 대해서 구하고 있었다. 문제에서는 도착 지점까지 가기 위해 다리가 무너지지 않게 최대로 들고 갈 수 있는 가중치를 구하는 것이었다. 문제를 제대로 이해하지 않고 풀어서 시간안에 해결을 못하고 결국에 틀렸다. 밑에 코드는 시험이 끝나고 다시 한 번 작성해본 코드이다.

참고
풀이 방법은 굉장히 다양했다. union-find 방식으로도 푼 사람도 있고 이분탐색 + BFS 방식으로도 푼 사람이 있다. 그 두 코드는 올리지는 않고 다음에 한번 구현할 생각이다.

from sys import stdin
from heapq import heappop, heappush

# INF: 10억으로 설정
INF = int(1e9)
input = stdin.readline

# N: 섬 위치, M: 다리의 정보
N, M = map(int, input().split())
# 다리의 정보 그래프
graph = [[] for _ in range(N + 1)]
# 다리의 정보 그래프 양방향 초기화
for _ in range(M):
    A, B, C = map(int, input().split())
    graph[A].append([B, C])
    graph[B].append([A, C])
    
# 시작 공장, 끝 공장
start_factory, end_factory = map(int, input().split())

# 최대 힙으로 다익스트라
def dijkstra(start_factory, end_factory):
    queue = []
    distance = [-INF] * (N + 1)
    heappush(queue, [0, start_factory])
    distance[start_factory] = 0
    
    while queue:
        dist, now = heappop(queue)
        dist = -dist
        
        if distance[now] > dist: continue
        
        if now == end_factory: return distance[now]
        
        for x, cost in graph[now]:
        	# 맨 처음으로 들어온 경우 0일때 위해서 작성
            cost = cost if not dist else min(dist, cost)
            if cost > distance[x]:
                distance[x] = cost
                heappush(queue, [-cost, x])

print(dijkstra(start_factory, end_factory))