100년 뒤 개발자 한승규입니다.

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

이 문제는 단순한 그래프 탐색이다.

하나 다른 문제들과 다른 점이 있다면, 아마 처음에 직사각형들을 색칠한다는 것?

그 후에는 그냥 단순히 넓이를 하나씩 입력해주고 그거를 그대로 출력해주면 끝난다.

from collections import deque
import sys
import heapq

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

result_list = list()

M, N, K = map(int, sys.stdin.readline().split())

paper = [[0 for _ in range(M)] for _ in range(N)]

for _ in range(K):
    start_x, start_y, end_x, end_y = map(int, sys.stdin.readline().split())

    for x in range(start_x, end_x):
        for y in range(start_y, end_y):
            paper[x][y] = 1

for x in range(N):
    for y in range(M):
        if paper[x][y] == 0:
            need_visit = deque()

            paper[x][y] = -1
            need_visit.append([x, y])

            result = 0

            while need_visit:

                cur_x, cur_y = need_visit.popleft()

                result += 1

                for i in range(4):
                    next_x, next_y = cur_x + dx[i], cur_y + dy[i]
                    if 0 <= next_x < N and 0 <= next_y < M and paper[next_x][next_y] == 0:
                        paper[next_x][next_y] = -1
                        need_visit.append([next_x, next_y])

            heapq.heappush(result_list, result)

print(len(result_list))

while result_list:
    print(heapq.heappop(result_list), end=' ')

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

BFS, DFS의 문제는 아니고 find와 union을 사용해서 해결하는 문제이다.

find 함수

def find(node):
    if parent[node] != node:
        parent[node] = find(parent[node])
    return parent[node]

해당 그래프에서 최상위 노드를 구해주는 함수이다.

만약 find로 구한 노드가 같으면, 같은 그래프에 속하는 노드인 것이다.

union 함수이다.

같은 그래프에 속하지 않는 노드들을 연결해주는 함수이다.

def union(node1, node2):
    root1 = find(node1)
    root2 = find(node2)

    if rank[root1] > rank[root2]:
        parent[root2] = root1
    else:
        parent[root1] = root2
        if rank[root1] == rank[root2]:
            rank[root2] += 1

이 함수들을 이용해서 같은 그래프에 속하는 노드끼리 묶어주고, 마지막에 여행을 가려는 노드들이 같은 그래프에 있는 지 확인을 해주면 된다.

import sys

N = int(sys.stdin.readline().strip())
M = int(sys.stdin.readline().strip())

parent = [i for i in range(N)]
rank = [0 for _ in range(N)]

city = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

trip = []

if M > 0:
    trip = list(map(int, sys.stdin.readline().split()))


def find(node):
    if parent[node] != node:
        parent[node] = find(parent[node])
    return parent[node]


def union(node1, node2):
    root1 = find(node1)
    root2 = find(node2)

    if rank[root1] > rank[root2]:
        parent[root2] = root1
    else:
        parent[root1] = root2
        if rank[root1] == rank[root2]:
            rank[root2] += 1


for i in range(N):
    for t in range(i):
        if city[i][t] == 1:
            if find(i) != find(t):
                union(i, t)

standard = find(trip[0] - 1)
flag = True

for i in range(1, M):
    if standard != find(trip[i] - 1):
        flag = False

print('YES' if flag else 'NO')

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

원래 푸는 방법대로 풀지 않은 거 같다.

원래는 1번 노드에서 가장 먼 곳을 찾은 후, 그 노드에서 가장 먼 곳과의 거리를 구하면 된다.

그러면 노드에서는 지름을 구할 수 있다.

하지만 그냥 아무생각없이 모든 노드를 방문하는 방법으로 풀었는데, 그냥 풀렸다.

그래서 이번 문제는 그냥 간단하게 푸는 방법으로 풀도록 하겠다.

이번에는 그래프를 dict로 받았는데, 모든 노드에 대한 2차원 배열로 만들면 메모리 초과가 발생한다.

그냥 반복마다, 최대의 길이를 구하고 그 중에서 최대의 길이를 출력한다.

import sys
from collections import deque

n = int(sys.stdin.readline().strip())

node = {i: [] for i in range(n)}

for i in range(n - 1):
    start, end, weight = map(int, sys.stdin.readline().split())

    node[start - 1].append([end - 1, weight])
    node[end - 1].append([start - 1, weight])

result = 0

for i in range(n):
    cur_result = 0
    visited = [False for _ in range(n)]
    need_visit = deque()
    need_visit.append([0, i])
    visited[i] = True

    while need_visit:

        cur_weight, cur_node = need_visit.popleft()

        cur_result = max(cur_result, cur_weight)

        for next_node, next_weight in node[cur_node]:
            if visited[next_node] is False:
                visited[next_node] = True
                need_visit.append([cur_weight + next_weight, next_node])

    result = max(result, cur_result)

print(result)

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

평범한 그래프 문제였지만, 이동이 있었는지 체크하며 수를 하나씩 늘리는 과정이 좀 귀찮았다.

한 차례마다 각 칸에 대하여

위, 아래, 좌, 우 이렇게 4방향을 확인하고 만약 차이가 범위 내라면 그래프 탐색을 실행한다.

탐색을 진행하가며 인구수를 더해주고 탐색이 끝나면 총 인구를 칸으로 나누어 인구를 분배한다.

만약 해당 차례에 인구의 이동이 없었다면, 반복문을 종료하고 지금까지 소모한 턴을 출력한다.

import sys
from collections import deque

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

N, L, R = map(int, sys.stdin.readline().split())

nation = list()

for _ in range(N):
    nation.append(list(map(int, sys.stdin.readline().split())))

flag = True

result = 0

while flag:

    flag = False

    visited = [[False for _ in range(N)] for _ in range(N)]

    for r in range(N):
        for c in range(N):
            if visited[r][c] is False:

                visited[r][c] = True

                need_visit = deque()
                change = [[r, c]]

                need_visit.append([r, c])

                people = nation[r][c]

                while need_visit:

                    cur_r, cur_c = need_visit.popleft()

                    for d in range(4):
                        next_r, next_c = cur_r + dx[d], cur_c + dy[d]
                        if 0 <= next_r < N and 0 <= next_c < N and visited[next_r][next_c] is False and L <= abs(nation[cur_r][cur_c] - nation[next_r][next_c]) <= R:
                            change.append([next_r, next_c])
                            visited[next_r][next_c] = True
                            need_visit.append([next_r, next_c])
                            people += nation[next_r][next_c]
                            flag = True

                per_people = people // len(change)

                for next_r, next_c in change:
                    nation[next_r][next_c] = per_people

    if flag:
        result += 1

print(result)

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

백준의 숨바꼭질 문제와 굉장히 비슷하다.

그냥 단순히 배열을 만들어서 BFS로 풀면 끝난다.

import sys
from collections import deque

F, S, G, U, D = map(int, sys.stdin.readline().split())

stair = [float('inf') for _ in range(F + 1)]
stair[S] = 0

need_visit = deque()

need_visit.append(S)

while need_visit:

    cur_stair = need_visit.popleft()

    if cur_stair == G:
        break

    next_up, next_down = cur_stair + U, cur_stair - D

    next_cnt = stair[cur_stair] + 1

    if 0 < next_up <= F and stair[next_up] > next_cnt:
        stair[next_up] = next_cnt
        need_visit.append(next_up)

    if 0 < next_down <= F and stair[next_down] > next_cnt:
        stair[next_down] = next_cnt
        need_visit.append(next_down)


print(stair[G] if stair[G] != float('inf') else "use the stairs")

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

원래 상하좌우 4방향만 움직이던 그래프에서 나이트가 이동하는 8방향으로 이동 할 수 있도록 방향을 설정해주면 된다.

여기에는 못 가는 경우가 있을 줄 알았는데... 고려하지 않고 그냥 제출해도 맞다고 되는 것을 보니, 못 가는 경우가 존재하지 않는 것 같다.

그냥 Python3로 제출하면 시간초과가 발생하고 Pypy3로 제출했었다.

그냥 방향만 추가가 되었고, 푸는 방법은 기존과 다르지 않으니 더 설명은 하지 않도록 하겠다.

from collections import deque
import sys

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

for _ in range(int(sys.stdin.readline())):
    i = int(sys.stdin.readline().strip())

    start_y, start_x = map(int, sys.stdin.readline().split())

    dest_y, dest_x = map(int, sys.stdin.readline().split())

    visited = [[float('inf') for _ in range(i)] for _ in range(i)]
    visited[start_y][start_x] = 0

    need_visit = deque()

    need_visit.append([0, start_y, start_x])

    result = -1

    while need_visit:

        cur_cnt, cur_y, cur_x = need_visit.popleft()

        if cur_y == dest_y and cur_x == dest_x:
            result = cur_cnt

        for index in range(8):
            next_y, next_x = cur_y + dy[index], cur_x + dx[index]
            if 0 <= next_y < i and 0 <= next_x < i and visited[next_y][next_x] > cur_cnt + 1:
                need_visit.append([cur_cnt + 1, next_y, next_x])
                visited[next_y][next_x] = cur_cnt + 1

    print(result)

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

해당 문제의 분류는 분명 그래프에 너비 우선 탐색이겠지만, 딱 보자마자 플로이드 와샬이 생각이 나서 해당 방법으로 해결했다.

n * n 크기의 배열을 만들고 3중 반복문으로 각 촌수를 계산할 수 있도록 하였다.

import sys

n = int(sys.stdin.readline().strip())

target_a, target_b = map(int, sys.stdin.readline().split())

family = [[float('inf') for _ in range(n)] for _ in range(n)]

for _ in range(int(sys.stdin.readline().strip())):
    a, b = map(int, sys.stdin.readline().split())
    family[a-1][b-1] = 1
    family[b-1][a-1] = 1

for i in range(n):
    for t in range(n):
        for k in range(n):
            if t != k:
                family[t][k] = min(family[t][k], family[t][i] + family[i][k])


print(family[target_a - 1][target_b - 1] if family[target_a - 1][target_b - 1] != float('inf') else -1)

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

구현 과정이 굉장히 어려웠던 문제이다.

우선 처음에 정보를 입력받고 바로 반복문으로 현재 비버의 위치, 목적지, 물의 위치를 각각 배열과 변수에 저장하였다.

그 후에는 당연히 BFS를 진행하였다.

한 턴이 반복 될 때마다 우선 물을 이동시킨다.

. 인 영역이면 물을 전파시켰고, 만약 전파가 되었다면 임시로 만든 deque에 저장하였으며 다음 턴에도 물의 전파를 위해 해당 턴이 끝나면 water deque에 임시 deque를 대입해주었다.

물의 전파가 끝나면 해당 턴에서 다시 비버를 이동시켜야 한다.

당연히 중복을 제거하기 위해 visited 배열을 사용했다.

deque에서 가능한 현재 비버의 위치를 가져왔으며, 만약 해당 위치가 목적지라면 반복문을 탈출 할 수 있도록 하였다.

비버의 위치를 가져온 후에는 4번의 반복을 통해 4 방향으로 이동시켜본 후 만약 해당 위치가 .이거나 목적지라면 visited = True로 바꾸어주고 다음 비버가 이동하기 위해 만든 next_move deque에 넣어준다.

이렇게 move에 데이터가 남아있을 동안 반복하고 모두 반복을 해도 도착하지 못하면 KAKTUS를 출력, 도착 했다면 결과를 출력하면 된다.

import sys
from collections import deque

R, C = map(int, sys.stdin.readline().split())

result = 0

move = deque()
water = deque()

target_r, target_c = -1, -1

arrive = False

forest = [list(sys.stdin.readline().strip()) for _ in range(R)]

for r in range(R):
    for c in range(C):
        if forest[r][c] == 'S':
            move.append([r, c])
            forest[r][c] = '.'
        elif forest[r][c] == 'D':
            target_r, target_c = r, c
        elif forest[r][c] == '*':
            water.append([r, c])


while move:

    # 물 먼저 이동
    next_water = deque()

    while water:

        cur_r, cur_c = water.popleft()

        for next_r, next_c in [[cur_r, cur_c - 1], [cur_r, cur_c + 1], [cur_r - 1, cur_c], [cur_r + 1, cur_c]]:
            if 0 <= next_r < R and 0 <= next_c < C and forest[next_r][next_c] == '.':
                forest[next_r][next_c] = '*'
                next_water.append([next_r, next_c])

    water = next_water

    # 비버 이동 가능 한 곳으로 이동

    next_move = deque()

    visited = [[False for _ in range(C)] for _ in range(R)]

    while move:

        cur_r, cur_c = move.popleft()

        if cur_r == target_r and cur_c == target_c:
            arrive = True
            break

        for next_r, next_c in [[cur_r, cur_c - 1], [cur_r, cur_c + 1], [cur_r - 1, cur_c], [cur_r + 1, cur_c]]:
            if 0 <= next_r < R and 0 <= next_c < C and (forest[next_r][next_c] == '.' or forest[next_r][next_c] == 'D') and visited[next_r][next_c] is False:
                next_move.append([next_r, next_c])
                visited[next_r][next_c] = True

    move = next_move

    if arrive:
        break

    result += 1

print(result if arrive else 'KAKTUS')