[백준 24955] 숫자 이어 붙이기

문제 출처 : https://www.acmicpc.net/problem/24955

24955번: 숫자 이어 붙이기

문제 이해하기

방문한 순서대로 숫자들을 이어 붙여서 출력하는 문제 입니다. 사실 이 문제는 LCA 항목에 있어서 LCA를 연습하려고 풀어본 문제인데 단순한 DFS로 해결되는 문제였습니다. 다만 이 문제에서 신경 쓸 부분은 두가지 입니다.

1. 숫자들 더해주는 것이 아니라 이어 붙이는 것입니다. 답을 숫자가 아닌 문자열로 관리해야 합니다.
2. 숫자가 너무 커지는 것을 방지하기 위해 나머지 연산을 합니다. 이 때 마지막에 한 번만 하는 것이 아니라 계속적으로 합니다.

이 두 가지만 신경써주면 쉽게 문제를 해결할 수 있습니다. 나머지 연산을 마지막에 한 번만 하지 않는 이유는 아래 링크에 설명을 해놓았습니다.

https://wikidocs.net/214915#_2

08. 나머지 연산

 

문제 풀이

그럼 문제를 같이 풀어보도록 하겠습니다.

입력 받기

import sys
input = sys.stdin.readline
mii = lambda : map(int, input().split())
MOD = 1_000_000_007

N, Q = mii()
arr = [''] + input().split()
tree = [[] for _ in range(N + 1)]

for _ in range(N - 1):
    u, v = mii()
    tree[u].append(v)
    tree[v].append(u)

입력 양이 많기 때문에 readline으로 입력 받는 속도를 높여주었습니다. readline 부분이 이해가 되지 않는다면 이전글을 확인 바랍니다.

2023.09.08 - [파이썬 팁] - 파이썬 입력 빠르게 받기

파이썬 입력 빠르게 받기

 

다음으로 나누어주어야할 숫자 MOD를 만들었습니다. 숫자에 언더바( _ )가 들어간 것이 이상하게 느껴질 수 있습니다. 숫자를 읽을 때 사용하는 콤마( , ) 와 같은 용도로 이해해 주면 됩니다. 언더바는 파이썬 내부에서 콤마처럼 숫자로 인식하지 않습니다. 즉 사용자가 숫자를 좀 더 편리하게 볼 수 있도록 해주는 것입니다.

이어붙일 숫자들을 저장할 arr은 문자로 입력 받습니다. 이 때 arr이 0이 아닌 1 부터 시작하게 하기 위해서 arr의 맨 앞에 빈 값인 ' ' 를 추가하였습니다.  마지막으로 N-1개의 간선을 입력 받아 Tree를 구성해 주었습니다.

정답 구하기

visited = []
ans = ''

for _ in range(Q):
    a, b = mii()
    visited = [False] * (N + 1)
    ans = ''
    dfs(a, b, '')
    print(ans)

Q번 동안 출력할 정답을 구해 줍니다. 이 때 dfs 함수를 사용할 예정이기 때문에 매 번 초기화 될 수 있도록 visited 값과 출력될 ans값을 초기화 해줍니다. dfs 함수를 실행해서 ans 값을 변경하고 그것을 출력해주면 됩니다. 

dfs 함수

이 문제의 핵심인 dfs 함수를 알아보겠습니다.

def dfs(s, e, num):
    global ans
    visited[s] = True
    num = str(int(num + arr[s]) % MOD)
        
    if s == e:
        ans = num
        return

    for nxt in tree[s]:
        if not visited[nxt]:
            dfs(nxt, e, num)

dfs 함수에는 3개의 인자가 들어갑니다. s는 시작 위치 start의 약자입니다. e는 도착해야 하는 위치 end의 약자 입니다. 마지막으로 num은 우리가 숫자를 이어붙여 만들어줄 결과값입니다. 앞에서 ans가 출력될 값이라고 했는데 dfs 함수에서 num을 따로 두었습니다. 두 값의 차이를 알아보겠습니다.

위 트리에서 1에서 시작해서 4로 도착한다고 했을 때 dfs 함수로 방문위치는 1 -> 2 -> 3 -> 4로 이어져 그대로 결과값을 만든다면 1234가 됩니다. 하지만 그 결과값이 우리가 원하는 값이 아닙니다. 우리가 원하는 값은 1 -> 3 -> 4로 이어지는 134가 되길 원합니다. 노드를 방문할 때마다 이전 결과에 추가되도록 하기 위해서 num이라는 인자를 따로 두어 만드는 것입니다. 1에서 2를 방문했을 때는 12가 되고, 1에서 3을 방문할 때는 13이 되고, 3에서 4를 방문 했을 때 134가 되게 하기 위해서 입니다. 그렇게 만든 값을 도착 위치 e에 왔을 때 ans로 바꿔주고 그 값을 출력해 주는 것입니다.

num은 문자이기 때문에 arr[s]값과 더해주고 그 값이 너무 커지지 않도록 숫자로 변경하여 MOD값으로 나누어 주었습니다. 그리고 최종적으로 다시 문자로 변경하여 넘겨주었습니다. 그래서 num값이 조금 복잡해 보입니다. 숫자로 관리하면 이어 붙일 때 어짜피 문자로 변경한 다음 이어 붙여야 하고, 문자로만 관리하면 마지막에 숫자가 너무 커져 속도가 느릴 수 있습니다. 복잡해 보이더라도 문자로 관리하고, 중간에 숫자로 변경해서 크기를 줄여주는 것이 관리하기 좋다고 생각했습니다.

그 외에는 기본적인 dfs 함수로 구성하면 쉽게 해결됩니다.

전체 코드

전체 코드를 확인해 보겠습니다.

import sys
input = sys.stdin.readline
mii = lambda : map(int, input().split())
MOD = 1_000_000_007

N, Q = mii()
arr = [''] + input().split()
tree = [[] for _ in range(N + 1)]
visited = []
ans = ''

for _ in range(N - 1):
    u, v = mii()
    tree[u].append(v)
    tree[v].append(u)

def dfs(s, e, num):
    global ans
    visited[s] = True
    num = str(int(num + arr[s]) % MOD)
        
    if s == e:
        ans = num
        return

    for nxt in tree[s]:
        if not visited[nxt]:
            dfs(nxt, e, num)

for _ in range(Q):
    a, b = mii()
    visited = [False] * (N + 1)
    ans = ''
    dfs(a, b, '')
    print(ans)