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())

import sys
import copy
from collections import deque

# sys.stdin = open('input.txt', 'r')

INPUT = sys.stdin.readline
DIRECTION = ((0, 1), (0, -1), (1, 0), (-1, 0))
N, M = map(int, INPUT().split())


def count_safe_area(board):
    cnt = 0
    for y in range(N):
        for x in range(M):
            if board[y][x] == 0:
                cnt += 1
    return cnt


def spread_virus(board, virus_zone):
    q = deque(virus_zone)
    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 < M and 0 <= next_y < N:
                if board[next_y][next_x] == 0:
                    board[next_y][next_x] = 2
                    q.append([next_x, next_y])


def find_all_cases(board, safe_zone):
    length = len(safe_zone)

    for i in range(length):
        for j in range(i + 1, length):
            for k in range(j + 1, length):
                tmp_board = copy.deepcopy(board)

                tmp_board[safe_zone[i][1]][safe_zone[i][0]] = 1
                tmp_board[safe_zone[j][1]][safe_zone[j][0]] = 1
                tmp_board[safe_zone[k][1]][safe_zone[k][0]] = 1
                yield tmp_board


def solution():
    """ 벽(1) 세 개를 세워서 바이러스(2)의 확산을 최대한 막습니다. 이 때, 안전 영역(0)의 최대 개수를 출력합니다.

    * 벽 세 개를 세울 수 있는 모든 경우의 수에 대해 아래 알고리즘을 단계별로 수행합니다.
     (1) 벽 세 개를 세울 수 있는 케이스를 생성합니다.
     (2) 바이러스를 퍼뜨립니다.
     (3) 바이러스를 퍼뜨렸을 때 안전 영역의 크기를 구합니다.
     (4) 최대 안전 영역의 크기로 갱신합니다.
     """
    board = [list(map(int, INPUT().split())) for _ in range(N)]
    safe_zone = []
    virus_zone = []
    res = -1

    for y in range(N):
        for x in range(M):
            if board[y][x] == 0:
                safe_zone.append([x, y])
            if board[y][x] == 2:
                virus_zone.append([x, y])

    # 핵심 알고리즘
    for case in find_all_cases(board, safe_zone):
        spread_virus(case, virus_zone)
        res = max(res, count_safe_area(case))
    return res
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)

solution 함수의 독스트링을 통해 알고리즘을 확인하시길 바랍니다!

import sys
from collections import deque


INPUT = sys.stdin.readline
N, M = map(int, INPUT().split())
BOARD = [list(map(int, INPUT().split())) for _ in range(N)]
DIRECTION = ((0, -1), (0, 1), (-1, 0), (1, 0))


def cheese_to_air(loc_list):
    """ BOARD에 있는 공기에 닿아 있는 치즈를 공기로 바꿈.

    * BOARD에서 0은 공기, 1은 치즈를 의미.
    """
    for x, y in loc_list:
        BOARD[y][x] = 0


def bfs():
    """ 공기에 닿아 있는 치즈의 좌표들을 구한 뒤, 리스트 형식로 리턴.

    * bfs로 구현함.
    - continue 조건: (1)좌표상 범위 (2)방문했던 좌표 (3)치즈를 만났을 때
    """
    outside_cheese_loc_list = []
    visited = [[0] * M for _ in range(N)]
    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

            visited[next_y][next_x] = 1

            if BOARD[next_y][next_x] == 1:
                outside_cheese_loc_list.append((next_x, next_y))
                continue

            q.append((next_x, next_y))
    return outside_cheese_loc_list


def solution():
    """ 공기와 닿은 치즈의 개수가 0이 될 때 까지 넓이 우선 탐색을 반복적으로 수행함.

    * 1회 반복에 발생하는 상태 변화
    (1) 공기와 맞닿은 치즈의 좌표 목록 구하기
    (2) 경과 시간(hour)이 1만큼 증가
    (3) 공기와 맞닿은 치즈들을 공기로 바꿈
    (4) 현재 치즈의 개수 저장


    while문 종료 후에 반복 수행된 횟수(hour)와 1시간 전 치즈의 개수를 출력(print)함.
    """
    hour = 0
    while outside_cheeses := bfs():
        hour += 1
        cheese_to_air(outside_cheeses)
        cheese_num_1hour_ago = len(outside_cheeses)
    print(hour)
    print(cheese_num_1hour_ago)


if __name__ == '__main__':
    solution()

문제 설명

- 첫 번째 줄에서는 주어질 데이터의 개수(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)

programmers.co.kr/learn/courses/30/lessons/42578

문제설명

1. 리스트에 1개 이상의 [의상의 이름, 의상의 종류]이 주어집니다.

ex) [[yellow_hat, headgear], [blue_sunglasses, eyewear], [green_turban, headgear]]

2. 최소 한 개 이상의 옷을 착용 한다고 했을 때, 착용 가능한 옷의 조합 수를 구해야 합니다.

 - 동일한 종류의 의상은 착용이 불가능합니다.

ex) 위의 예시에서 yellow_hat과 green_turban은 동시착용이 불가능합니다.

문제 풀이

1. 다음과 같은 테스트 케이스가 주어졌다고 가정합니다.

2. 입력받은 데이터는 딕셔너리로 표현될 수 있습니다. 

3. 착용할 수 있는 의상을 종류에 따라 트리로 정리하면 아래와 같습니다.

- 의상 종류별로 입을 수 있는 경우의 수는 "총 개수 + 1" 입니다.

  - 예를 들어, headgear에 관한 경우의 수는 "yellow_hat", "green_turban", "착용X"이 있습니다.

따라서 모든 종류의 의상을 착용하지 않는 경우의 수를 제외하면

(headergear의 개수+1) * (eyewear의 개수+1) -1이 정답으로 출력 됩니다.

코드

def solution(clothes):
    types = {}
    for v, k in clothes:
        types[k] = types.get(k, 0) + 1

    cnt = 1
    for _, v in types.items():
        cnt *= v+1
    return cnt-1

www.acmicpc.net/problem/14938

문제 설명

첫째 줄에는 지역의 개수(n), 수색 범위(m), 길의 개수(r)이 주어집니다.

둘째 줄에는 n개의 숫자가 차례대로 각 구역에 있는 아이템의 수를 나타냅니다.

세 번째 줄부터 r+2번째 줄 까지 지역의 번호 a, b와 길의 길이 i가 주어집니다.

이 때, 각 지역에서 수색 범위(m) 내에서 다른 지역으로 이동했을 때 얻을 수 있는 최대 아이템 개수를 구해야 합니다.

m이 5로 주어졌을 때 2번 지역에서는 "1번, 3번, 5번"으로 이동할 수 있습니다.

2번->1번->4번은 8(0+3+5)의 수색 범위를 가지므로 이동할 수 없습니다.

문제 특성

각 노드에서 다른 노드로 이동했을 때 최소 경로를 구해야 합니다.

따라서 다익스트라 알고리즘을 적용합니다.

알고리즘

1. 1 ~ n번 지역에서 다익스트라 알고리즘 수행  : 각 지역에서 다른 지역으로 이동했을 때 최소 경로를 구합니다.

3. 각 지역에서의 최소 경로 중 m 이하인 수색 범위의 구역에 있는 아이템 개수를 구합니다.

4. 이전 지역과 비교하여 더 많은 아이템 개수로 갱신합니다.

다익스트라 알고리즘

다익스트라 알고리즘의 전체 과정은 다음과 같습니다. 1번~4번 수행과정을 따라 알고리즘을 파악하시면 됩니다!

참고로 0번 인덱스의 [3, 5]에 대해 과정이 모두 수행된 다음에 [1, 3]에서 0(heap[1])과 더하고 dy와 비교하는 과정이 수행됩니다. 

이어서 각 리스트 변수에 대한 세부 사항을 설명하겠습니다.

1. graph는 각 노드 간의 정보를 담고 있습니다.

graph는 총 n 개의 길이를 가지며, 인덱스는 노드 번호를 의미합니다.

 - 문제에서 1번 지역을 graph에서는 0(1-1)번 인덱스로 담았습니다.

또한, graph의 각 인덱스는 복수 개의 [인접한 노드번호, 거리]를 가질 수 있습니다.

2. dy는  한 지역에서 다른 지역으로 이동할 때 최소 거리를 담고 있습니다.

 - dy는 총 n 개의 길이를 가지며, 인덱스는 노드 번호를 의미합니다.

 - dy의 인덱스 초기 값은 int의 최대 값으로 설정합니다. 이 값은 지역 간 이동할 수 있는 최소 거리를 의미합니다.

 - 가령, 2번 지역에서 4번 노드로 이동할 때는 8(3+5)이 최소거리입니다.  따라서 알고리즘이 수행된 후에 dy의 1번 인덱스는 8이 리턴되어야 합니다.

3. heap는  다른 지역으로 이동할 때, 중간 경로의 역할을 수행합니다.

- heap에 들어가는 초기 값은 (출발 지역 번호, 0)입니다. 뒤에 있는 0은 이동해야 하는 거리를 의미합니다.

  - 가령 3번 지역에서 출발한다면  (2, 0) 입니다. (출발 지역 번호-1이므로) 

  - 0번에서 0번을 이동하므로, 초기 거리는 0입니다.

- heap 리스트가 비었을 때 다익스트라 알고리즘은 종료됩니다.

코드

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


def dijstra(x):
    dy = [sys.maxsize] * n
    dy[x] = 0
    heap = [[x, dy[x]]]
    while heap:
        node, dis = heapq.heappop(heap)
        for i in range(len(graph[node])):
            next = graph[node][i]
            if dy[next[0]] > dis + next[1]:
                dy[next[0]] = dis + next[1]
                heapq.heappush(heap, [next[0], dis + next[1]])
    return dy

if __name__ == "__main__":
    n, m, r = map(int, input().split())  # 지역의 개수, 수색범위, 길의 개수
    numItem = list(map(int, input().split()))  # 인덱스는 지역 번호를 의미
    graph = [[] for _ in range(n)]
    for _ in range(r):
        a, b, i = map(int, input().split())  # 연결된 지역의 번호(a, b), 길의 길이(i)
        graph[a - 1].append([b - 1, i])
        graph[b - 1].append([a - 1, i])
    res = 0
    for i in range(n):    # 각 노드에서 최소 경로탐색
        minPath = dijstra(i)
        add = 0
        for j in range(n):    # 최소 경로가 m 이하일 때 획득할 수 있는 아이템 수
            if minPath[j] <= m:
                add += numItem[j]
        res = max(res, add)
print(res)

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)