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

두 가지 방식으로 코드를 작성했다.

내용은 같은데, A 코드는 컴프리헨션을 사용했고 B 코드는 이중 for문으로 작성했다.

개인적으로 A 코드가 더 마음에 든다. 

두 줄로 작성 했음에도 가독성이 더 낫다.

B 코드에서는 수 세기, 타입 변환 등 잡음이 많아서 어수선하다.

A 코드

# A 코드: 시간 68ms, 메모리 29200 KB

import sys

INPUT = sys.stdin.readline    # 10+01-1+1


def solution(exp):
    """ 주어진 식에 적절히 괄호를 쳐서 최소 값으로 계산하여 리턴한다.
    """
    numbers = [sum(map(int, x1.split('+'))) for x1 in exp.split('-')]
    return numbers[0] - sum(numbers[1:])

print(solution(INPUT()))

B 코드

# B코드 : 시간 72ms, 메모리 29200 KB

import sys

INPUT = sys.stdin.readline    # 10+01-1+1


def solution():
    """ 주어진 식에 적절히 괄호를 쳐서 최소 값으로 계산하여 리턴한다.

    """
    exp = INPUT().split('-')

    numbers = []
    for x1 in exp:
        x2 = x1.split('+')

        count = 0
        for num in x2:
            count += int(num)

        numbers.append(count)
    return numbers[0] - sum(numbers[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())

두 가지 다른 리스트 구조로 풀었습니다. 그랬더니 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 heapq

MAX_TIME = 500001


def solution(N, road, K):
    # 1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 return 하면 됩니다.

    graph = [[] for _ in range(N)]
    for a, b, c in road:
        graph[a - 1].append([b - 1, c])
        graph[b - 1].append([a - 1, c])

    minimum_time_per_nodes = [MAX_TIME] * N

    heapq.heappush(q := [], [target_to_q := 0, curr_time := 0])
    minimum_time_per_nodes[0] = 0
    while q:
        target_to_q, curr_time = heapq.heappop(q)
        for target_to_mtpn, time in graph[target_to_q]:
            if (expect_time := curr_time + time) > K:
                continue
            if expect_time >= minimum_time_per_nodes[target_to_mtpn]:
                continue
            minimum_time_per_nodes[target_to_mtpn] = expect_time
            heapq.heappush(q, [target_to_mtpn, expect_time])
    return len([x for x in minimum_time_per_nodes if x < MAX_TIME])


if __name__ == '__main__':
    # N = 5
    # road = [[1, 2, 1], [2, 3, 3], [5, 2, 2], [1, 4, 2], [5, 3, 1], [5, 4, 2]]
    # K = 3

    N = 6
    road = [[1, 2, 1], [1, 3, 2], [2, 3, 2], [3, 4, 3], [3, 5, 2], [3, 5, 3], [5, 6, 1]]
    K = 4
    print(solution(N, road, K))

import sys
INPUT = sys.stdin.readline


def solution():
    """  최소 값을 갖는 생성자를 리턴한다.

    *  245      ->  245 + (2 + 4 + 5)
    *  생성자(M) ->  분해합(N)

    (1) 1 ~ n-1 해당하는 범위의 값에 대해 각각 분해합을 구한다.
    (2) 최초로 발견되는 생성자를 답으로 리턴한다. 답이 없으면, 0을 리턴한다.
    """
    for m in range(1, n := int(INPUT())):
        if (get_n := m + sum(map(int, str(m)))) == n:
            return m
    return 0


if __name__ == '__main__':
    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)