Jin의 일상

BFS에 조금 변형을 줘서 풀 수 있는 문제다.

일반적으로 BFS는 큐 자료구조를 통해 풀 수 있다.

큐는 선입 선출(FIFO)이므로, 기본 컨셉에 따르면 맨 뒤에 새로운 값을 넣어준 뒤 맨 앞에서 값을 빼내야 한다.

그런데 이 문제의 특정 조건에서는 큐의 맨 앞에 새로운 값을 넣어준다.

이 방법을 통해 우선적으로 탐색되어야 할 좌표에 가중치를 부여한 것이다.

어쨌든, 인풋되는 방식만 다를 뿐 알고리즘은 똑같이 작동한다.

나는 두 가지 방식으로 알고스팟 문제를 풀었는데, 앞에서 설명한 것이 A 방식이다.

B 방식은 다음 좌표의 값이 현재 좌표의 값보다 작다면 이동하는 방식을 취하고 있다.

전형적인 BFS에 조건을 하나 추가한 것이다.  하지만 채점의 63%정도 구간에서 메모리 초과로 테스트를 통과하지 못했다. 그래도 테스트 케이스는 모두 통과할 것으로 생각된다.

메모리 초과한 원인을 분석하기 위해 BFS 진행 간 A와 B 방식의 Queue 값을 출력했다.

A 코드는 우선적으로 탐색해야 할 좌표에 가중치를 부여했으므로, 불필요한 탐색이 깊게 진행되지 않았다. 

반면에 B 코드는 이전에 4번의 벽을 부수고 이동했는데, 이번에 3번 벽을 이동한 경로가 발견됐다면 3으로 갱신하고 다음 번에 1번만 벽을 부수어도 된다면 다시 갱신하고,. ..... 이렇게 반복해야 한다. 따라서 불필요한 탐색이 깊게 진행된다.

그래서 Queue에 저장될 좌표도 많아질 수 밖에 없던 것이다.

A 코드

# A 코드: 좌표의 상태에 따라 가중치를 부여함 

import sys
from collections import deque

INPUT = sys.stdin.readline
DIRECTION = ((0, 1), (0, -1), (1, 0), (-1, 0))


def solution():
    m, n = map(int, INPUT().split())
    board = [list(map(int, INPUT().rstrip())) for _ in range(n)]
    visited = [[-1] * m for _ in range(n)]

    visited[0][0] = 0
    q = deque([[0, 0]])
    while q:
        x, y = q.popleft()

        for i in range(4):
            next_x = x + DIRECTION[i][0]
            next_y = y + DIRECTION[i][1]

            if (0 > next_x or next_x >= m) or (0 > next_y or next_y >= n):
                continue

            if visited[next_y][next_x] != -1:
                continue

            if board[next_y][next_x] == 0:
                visited[next_y][next_x] = visited[y][x]
                q.appendleft([next_x, next_y])
            else:
                visited[next_y][next_x] = visited[y][x] + 1
                q.append([next_x, next_y])
    return visited[n-1][m-1]
print(solution())

B 코드 

# B 코드: 좌표별 상태에 따라 가중치를 부여하지 않음. (메모리 초과)

import sys
from collections import deque

INPUT = sys.stdin.readline
MAX = 9999999
DIRECTION = ((0, 1), (0, -1), (1, 0), (-1, 0))


def solution():
    m, n = map(int, INPUT().split())
    board = [list(map(int, INPUT().rstrip())) for _ in range(n)]
    visited = [[MAX] * m for _ in range(n)]

    visited[0][0] = 0
    q = deque([[0, 0]])
    while q:
        x, y = q.popleft()

        for i in range(4):
            next_x = x + DIRECTION[i][0]
            next_y = y + DIRECTION[i][1]

            if (0 > next_x or next_x >= m) or (0 > next_y or next_y >= n):
                continue

            if visited[next_y][next_x] <= visited[y][x]:
                continue

            if board[next_y][next_x] == 0:
                visited[next_y][next_x] = visited[y][x]
                q.appendleft([next_x, next_y])
            else:
                visited[next_y][next_x] = visited[y][x] + 1
                q.append([next_x, next_y])
    return visited[n-1][m-1]
print(solution())

두 가지 다른 리스트 구조로 풀었습니다. 그랬더니 25% 더 빨라졌습니다. 메모리는 42% 개선됐구요.
같은 코드더라도 답을 제출할 때 마다 시간 효율이 다르게 측정되긴 하지만 꽤 큰 차이라서 기록합니다!

아래와 같이 노드가 주어졌다고 가정해보겠습니다.

A 코드는 그래프에 값을 담을 때 연결된 정점만 담습니다.
[[1, 4],
[0, 4, 3, 2],
[3, 1],
[2, 5, 4, 1],
[1, 0, 3],
[3]]

B 코드는 모든 노드와의 연결을 1(연결 됐음)과 0(안됐음)으로 표현합니다.
[[0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 1, 0],
[0, 1, 0, 1, 1, 1, 0],
[0, 0, 1, 0, 1, 0, 0],
[0, 0, 1, 1, 0, 1, 1],
[0, 1, 1, 0, 1, 0, 0],
[0, 0, 0, 0, 1, 0, 0]]


현재까지 알아낸 바로는 리스트에 append할 때 더 많은 런타임이 발생합니다.
A와 B 코드의 입력 방식에 따른 런타임 시간을 비교한 코드입니다.

import time
R = 10000000


# A 코드 : 연결된 정점만 담음.
c = time.time()
t2 = []
for i in range(R):
    t2.append(i)
d = time.time()
assert d - c == 1.2  # 물론 항상 다름^^


# B 코드 : 각 노드의 연결 여부를 0과 1로 표현
a = time.time()
t1 = [0] * R
for i in range(R):
    t1[i] = i
b = time.time()
assert b - a == 0.64  # 물론 항상 다름^^

A 코드

# A 코드: 메모리 63920 KB, 시간 728 ms
import sys
sys.setrecursionlimit(10000)
INPUT = sys.stdin.readline


def dfs(graph, visited, n):
    visited[n] = 1
    for i in graph[n]:
        if visited[i] == 0:
            dfs(graph, visited, i)


def solution():
    vertex_num, edges_num = map(int, INPUT().split())

    graph = [[] for _ in range(vertex_num)]
    for _ in range(edges_num):
        a, b = map(int, INPUT().split())
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)

    cnt = 0
    visited = [0] * vertex_num
    for i in range(vertex_num):
        if visited[i] == 0:
            cnt += 1
            dfs(graph, visited, i)
    return cnt

print(solution())

B 코드

# D 코드: 메모리 37012KB, 시간 552ms
import sys
sys.setrecursionlimit(10000)
sys.stdin = open('input.txt', 'r')

INPUT = sys.stdin.readline


def dfs(i, graph, visited, vertex_num):
    visited[i] = True
    for j in range(1, vertex_num + 1):
        if visited[j]:
            continue
        if graph[i][j] == 0:
            continue
        dfs(j, graph, visited, vertex_num)


def solution():
    vertex_num, edges_num = map(int, INPUT().split())
    graph = [[0] * (vertex_num + 1) for i in range((vertex_num + 1))]
    visited = [0] * (vertex_num + 1)

    for i in range(edges_num):
        a, b = map(int, INPUT().split())
        graph[a][b] = 1
        graph[b][a] = 1

    cnt = 0
    for i in range(1, vertex_num + 1):
        if visited[i] == 0:
            cnt += 1
            dfs(i, graph, visited, vertex_num)
    return cnt
print(solution())

import sys
from itertools import combinations
# sys.stdin = open('input.txt', 'r')

INPUT = sys.stdin.readline


def solution():
    # 카드 세 장의 합(x)이 가장 큰 값을 리턴한다. (조건: x <= m)

    num_cards, m = map(int, INPUT().split())
    cards = map(int, INPUT().split())

    sum_3_each_cards = (a + b + c for a, b, c in combinations(cards, 3))

    res = -1
    for x in sum_3_each_cards:
        if x == m:
            return x
        if x > m:
            continue
        res = max(res, x)
    return res


if __name__ == '__main__':
    print(solution())

풀이

import sys
INPUT = sys.stdin.readline


def remove_node(tree, parents, n):
    """ 요청받은 노드를 제거 합니다.

    1. tree 내에 자신(n)을 자식으로 나타내는 부모 노드에서 n을 지웁니다.
      -> parents[n] == -1은 루트 노드이므로 부모 노드가 없습니다.
    2. 재귀적으로 자식 노드를 지웁니다. 지워진 자식 노드의 tree 내에 값을 [-1]로 표기합니다.
    """
    if parents[n] != -1:
        tree[parents[n]].remove(n)

    def remove_child(x):
        for i in tree[x]:
            remove_child(i)
        tree[x] = [-1]
    remove_child(n)


def solution():
    """ 자식이 없는 노드의 개수를 출력합니다.

    1. 이중 리스트(tree)를 생성하고 자신의 자식 노드 인덱스를 넣습니다.
      -> 문제에서 주어진 값 중 -1은 부모 노드가 없음을 의미합니다.
    2. 문제에서 주어진 노드를 제거합니다.
    3. tree에서 자식이 없는 노드([], 빈 노드)의 개수를 출력합니다.
    """
    node_num = int(INPUT())
    parents = list(map(int, INPUT().split()))
    tree = [[] for _ in range(node_num)]

    for i in range(node_num):
        if parents[i] == -1:
            continue
        tree[parents[i]].append(i)

    remove_node(tree, parents, node_to_remove := int(INPUT()))
    return tree.count([])

if __name__ == '__main__':
    print(solution())

반례: ValueError 발생 원인

풀이 과정에서 ValueError가 발생했습니다. 0번 인덱스는 루트 노드(-1)라는 가정했기 때문입니다.

이에 대해 아래와 같은 반례를 고려해볼 수 있습니다.

5

1 2 3 4 -1

4

런타임 발생 당시 코드 일부입니다. n != 0을 확인해주시기 바랍니다. 이를 parents[n] != -1으로 수정했습니다.

import sys
INPUT = sys.stdin.readline


def remove_node(tree, parents, n):
    """ 요청받은 노드를 제거 합니다.

    1. tree 내에 자신(n)을 자식으로 나타내는 부모 노드에서 n을 지웁니다.
      -> n == 0은 루트 노드이므로 부모 노드가 없습니다.
    2. 재귀적으로 자식 노드를 지웁니다. 지워진 자식 노드의 tree 내에 값을 [-1]로 표기합니다.
    """
    if n != 0:
        tree[parents[n]].remove(n)

    def remove_child(x):
        for i in tree[x]:
            remove_child(i)
        tree[x] = [-1]
    remove_child(n)

문제 설명

- 첫 번째 줄에서는 주어질 데이터의 개수(N)가 주어진다.

- 다음 줄에는 N개의 데이터가 주어진다. (1 <= N <= 500,000)

- 시간 제한  1초

출력 : 숫자 간 교환이 일어난 횟수를 구해야 한다.

버블 정렬 예시

(1) 321 : 3 2 1 => 2 3 1  => 2 1 3 => 1 2 3

(2) 4253 : 4 2 5 3 => 2 4 5 3=> 2 4 3 5 => 2 3 4 5

문제 풀이

(1) 어떤 정렬 알고리즘을 사용할지?

버블 소트는 N 제곱의 시간 복잡도를 가진다.

문제 조건에 따르면 최대 25 * (10^10)의 시간 복잡도를 가진다.

파이썬의 1초당 계산 가능 횟수는 2 * (10^7)이므로, 버블 소팅으로는 문제를 풀 수 없다.

따라서 다른 방식의 정렬을 이용해야 한다.

병합정렬을 이용하면 N * log(N)의 시간복잡도가 소요된다. 

5*(10^5) * log(5*(10^5))이므로, 시간 복잡도는 해결이 된다.

(2) 숫자 간 교환 횟수를 어떻게 구할지?

버블 정렬에서는, 

1. 두 요소 간 순서가 맞으면 가만히 두고

2. 순서가 틀렸다면 숫자를 교환한다.

2번에 착안해서 버블 정렬에서 정렬하는 과정을 살펴보자.

1. 위 그림의 맨 밑에 줄부터 A와 B를 비교해서 B가 작으면 교환이 일어난다.

이 때, 교환될 숫자의 개수는 CNT에 더해주자. (남은 A의 개수만큼 더해주면 된다.)

[3] [1] => [1, 3]           [2] [4] => [2, 4]

CNT += len(A)

2. [1, 3] [2, 4]를 비교한다. 

A의 맨 앞과 B의 맨 앞을 비교했을 때, A가 작으므로, A의 1이 빠진다.

[1,3] [2, 4] => [3] [2, 4],  [1]

3. A의 맨 앞과 B의 맨 앞을 비교했을 때, B가 작으므로, B의 2가 빠진다.

B가 작으면, 스와핑이 일어나야 하므로 남은 A의 총 길이를 CNT에 더해준다. 

[3] [2, 4] => [3] [4],  [1, 2]

CNT += len(A)

4. A의 맨 앞과 B의 맨 앞을 비교했을 때, A가 작으므로, A의 3이 빠진다.

[3] [4], => [] [4], [1, 2, 3]

5. A에 들어있던 모든 원소가 빠졌으므로, B에 남은 원소를 추가한다

[] [4] => [] [], [1, 2, 3, 4]

6. 스와핑이 일어난 횟수(CNT):  2

반례

문제에는 동일한 원소가 나오지 않는다는 조건이 없다.

즉, 3 2 5 3 4와 같은 경우가 있을 수 있다.

이를 고려하여 코드를 작성해야 한다.

코드

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


def mergeSort(start, end):
    global cnt
    if start < end:
        mid = (start + end) // 2
        mergeSort(start, mid)
        mergeSort(mid + 1, end)

        a = start
        b = mid + 1
        tmp = []
        while a <= mid and b <= end:
            if arr[a] <= arr[b]:
                tmp.append(arr[a])
                a += 1

            else:
                tmp.append(arr[b])
                b += 1
                cnt += (mid - a + 1)  # 스와핑 했을 때 개수추가
        if a <= mid:
            tmp = tmp + arr[a:mid+1]
        if b <= end:
            tmp = tmp + arr[b:end+1]

        for i in range(len(tmp)):
            arr[start + i] = tmp[i]

if __name__ == '__main__':
    cnt = 0
    n = int(input())
    arr = list(map(int, input().split()))
    mergeSort(0, n-1)
    print(cnt)

문제 설명

일반 알파벳 순서와 달리 민식어는 "a b k d e g h i l m n ng o p r s t u w y" 순서를 따릅니다.

민식어 중 ng는 하나의 알파벳으로 간주됩니다.

민식어로 만든 n개의 단어가 주어졌을 때, 민식어를 기준으로 순서대로 리턴합니다.

알고리즘

1. 딕셔너리의 키를 민식어로 두고, 순서에 따라서 값으로 알파벳을 정의합니다. (문자를 기준으로 정렬하기 때문에 숫자로 값을 정의하면 12 > 101와 같은 경우가 발생합니다. )

 - 민식어 중에서 "ng"는 "z"와 같이 민식어에 포함되지 않는 알파벳을 정의합니다.

2. 민식어로 만든 단어들을 입력받고, 각 단어에서 "ng"를 찾아서 다른 알파벳으로 바꿉니다. 알고리즘 1번에서 언급했듯이 민식어에 포함되지 않는 알파벳으로 선택해야 합니다.

3. 반복문으로 민식어로 만든 문자를 한 글자씩 추출하여 딕셔너리의 키 값으로 넣습니다. value로 나온 것을 더하여 알파벳으로 치환합니다.

4. 민식어에서 알파벳으로 치환된 문자는 여러 개의 민식어가 저장된 리스트의 인덱스 번호와 함께 새로운 리스트에 담은 뒤, 문자를 기준으로 정렬합니다.

5. 정렬된 문자를 순서대로 뽑으며, 저장했던 인덱스 번호로 민식어를 출력합니다.

코드

import sys

# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

# key: ng => z (there is no 'z' in Minsik.)
minsik = {"a": 'A', "b": 'B', "k": 'C', "d": 'D', "e": 'E', "g": 'F', "h": 'G', "i": 'H', "l": 'I', "m": 'J', "n": 'K',
          "z": 'L', "o": 'M',
          "p": 'N', "r": 'O', "s": 'P', "t": 'Q', "u": 'R', "w": 'S', "y": 'T'}


n = int(sys.stdin.readline())
words = [sys.stdin.readline().rstrip() for _ in range(n)]

cvtWords = []
for i in range(n):
    word = words[i].replace('ng', 'z')
    cvtWord = ''
    for ch in word:
        cvtWord += minsik[ch]
    cvtWords.append([cvtWord, i])
cvtWords.sort(key=lambda x: x[0])
for _, i in cvtWords:
    print(words[i])

www.acmicpc.net/problem/13458

문제

세 줄로 데이터가 주어진다.

각 줄은 시험장의 개수 (n), 각 시험장의 응시자 수 (a), 총 감독관 역량(b), 부 감독관 역량(c)를 의미한다.

 - b와 c는 감독 가능한 응시자 수를 의미한다.

총감독관은 각 시험장에 최소 한 명 들어가야 하며, 부 감독관은 여러 명이 들어가도 된다.

이 때, 모든 응시자를 감독하기 위한 감독관의 수를 구해야 한다.

알고리즘

1. 시험장에는 최소 한 명의 총 감독관이 들어가야 한다.  따라서 각 시험장의 응시자 수에서 b를 뺀다.

 (1) n - b <= 0인 경우에는 정답으로 제출할 총 감독관 수에 1을 더한다.

   한 명의 총 감독관이 모든 응시자를 감독할 수 있으므로, 부 감독관이 필요없기 때문이다.

 (2) n - b > 0인 경우에는 2번으로 넘어간다.

2. n - b를 한 값에 부 감독관의 역량인 c를 나누어 준다.

 (1) 나머지가 있는 경우에는 정답으로 제출할 총 감독관 수에 3을 더해준다.

   - 총 감독관 1명 + 부 감독관 2명

 (2) 나머지가 없는 경우에는 정답으로 제출할 총 감독관 수에 2를 더해준다.

  - 총 감독관 1명 + 부 감독관 1명

코드

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

n = int(input())
a_list = list(map(int, input().split()))
b, c = map(int, input().split())

cnt = 0
for i in range(n):
    tmp = a_list[i] - b
    if tmp <= 0:
        cnt += 1
    else:
        q, r = divmod(tmp, c)
        if r == 0:
            cnt += (q + 1)
        else:
            cnt += (q + 2)
print(cnt)

www.acmicpc.net/problem/10775

문제 설명

1. G개의 게이트 수가 주어진다.

2. P개의 비행기는 순차대로 날아오며, 비행기마다 i값을 갖는다.

3. 비행기는 1~G(i) 게이트 중 하나에 주차된다.

 - 주차될 수 없다면, 더 이상 비행기가 공항으로 날아오지 않는다.

4. 가장 많은 비행기가 주차됐을 때 수는?

조건 범위

G (1 ≤ G ≤ 10^5)

P (1 ≤ P ≤ 10^5)

gi (1 ≤ gi ≤ G)

특이사항

반복문으로 이 문제를 풀 경우, 최대 10^5 * O(10^5)가 걸립니다. (10,000,000,000)

파이썬이 1초에 50,000,000 정도 계산한다고 가정했을 때, 반복문으로 풀면 안됩니다.

따라서 이 문제는 "유니온-파인드"를 이용해서 해결해야 합니다.

알고리즘

총 6대의 비행기가 각 [4, 3, 2, 1, 4]의 값을 가지고 게이트에 날아온다고 가정하겠습니다.

1. 리스트를 만듭니다. 리스트 명은 gates로 정의하겠습니다. 또한, 각 인덱스의 값은 parent를 의미합니다.

 - 인덱스와 parent가 같다면, 주차장이 빈 상태임을 의미합니다.

 - 인덱스와 parent가 다르다면, 이미 비행기가 주차된 상태를 의미합니다.

2. i가 4인 비행기가 날아옵니다.

(2-1) gates의 4번 인덱스의 부모 노드를 확인합니다.

 - 부모노드는 4이므로, 해당 게이트에 주차되지 않은 상태입니다. 비행기를 4번 게이트에 주차시킵니다. (cnt 1 증가)

(2-2) 4번 게이트가 주차됐으므로, 한 칸 앞에 위치한 게이트의 부모노드를 값으로 수정합니다.

3. i가 3인 비행기가 날아옵니다.

 - 알고리즘 2번과 동일한 상황이므로, 3번 게이터에 주차(cnt 1 증가)시키고 앞에 위치한 부모노드 값으로 수정합니다.

4. i가 2인 비행기가 날아옵니다.

 - 알고리즘 2번과 동일한 상황이므로, 2번 게이터에 주차(cnt 1 증가)시키고 앞에 위치한 부모노드 값으로 수정합니다.

5. i가 1인 비행기가 날아옵니다.

 - 알고리즘 2번과 동일한 상황이므로, 1번 게이터에 주차(cnt 1 증가)시키고 앞에 위치한 부모노드 값으로 수정합니다.

6. i가 4인 비행기가 날아옵니다.

- gates의 4번 인덱스의 부모 노드를 확인합니다.

4번 인덱스의 부모노드는 자신의 값과 다릅니다. 즉, 4번 인덱스에는 비행기가 주차되어 있습니다.

따라서 4번 인덱스의 부모 노드로 이동합니다. 조금 전과 같은 상황이 연쇄적으로 반복됩니다.

재귀적으로 호출한 결과는 역순으로 리턴됩니다.

따라서 지나온 경로의 gates 인덱스는 부모 노드로 수정됩니다. 

참고로 지나온 경로를 이렇게 수정하는 테크닉을 "경로 단축"이라고 합니다.

경로 단축 테크닉을 사용하면 다음 번에 다시 i가 4인 비행기가 날아왔을 때

이번과 같이 O(N)경로를 지나지 않고 O(1)로 리턴할 수 있습니다.

방금 과정에서 4번 비행기가 날아왔을 때 0을 리턴했습니다.

이는 모든 게이트가 꽉 찼음을 의미합니다. 따라서 알고리즘을 종료합니다.

코드

import sys

sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


def find(n):
    if gates[n] == n:
        return n
    else:
        gates[n] = find(gates[n])
        return gates[n]


def union(a, b):
    x = find(a)
    y = find(b)
    gates[x] = y
    return

if __name__ == "__main__":
    numGate = int(input())
    numPlane = int(input())
    gates = list(range(numGate + 1))

    cnt = 0
    for _ in range(numPlane):
        gate = int(input())
        parent = find(gate)
        if parent == 0:
            break
        union(parent, parent-1)
        cnt += 1
    print(cnt)