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/1167

트리의 지름을 구하는 방법은 우선, 한 노드에서 가장 멀리 있는 노드를 구한다.

그리고 그 노드에서 가장 멀리 있는 길이를 구한다.

그러면 그게 노드의 지름이 된다.

그러면 2번 길이를 구해야 하는 데, 귀찮아서 함수로 만들어버렸다.

우선 각 그래프에 대한 정보를 입력 받은 후 BFS를 진행한다.

처음의 BFS에서는 가장 멀리 있는 노드를 구하고, 그 다음의 BFS에서는 길이를 구한 후 출력한다.

from collections import deque
import sys

V = int(sys.stdin.readline())

graph = [[] for _ in range(V + 1)]

for _ in range(V):
    c = list(map(int, sys.stdin.readline().split()))
    for e in range(1, len(c) - 2, 2):
        graph[c[0]].append((c[e], c[e + 1]))


def bfs(target):
    weight = [-1] * (V + 1)
    weight[target] = 0
    need_visit = deque()
    need_visit.append(target)
    result = [0, 0]

    while need_visit:
        cur = need_visit.popleft()
        for v, w in graph[cur]:
            if weight[v] == -1:
                weight[v] = weight[cur] + w
                need_visit.append(v)
                if result[0] < weight[v]:
                    result = [weight[v], v]

    return result


print(bfs(bfs(1)[1])[0])

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)