백준(BOJ) 25498 핸들 뭘로 하지(Python)

 

문제 내용

대표

 

BFS 문제.

1번 노드부터 시작해서 갈 수 있는 노드 중 가장 사전 순으로 뒤에 있는 문자로 이동하면서 ans에 그 문자를 추가해주면 된다.

만약 그 문자를 가진 노드가 2개 이상인 경우 그 문자를 가진 모든 노드에 대해 탐색을 진행해야 한다.

이를 해결하기 위해 한 노드에서 갈 수 있는 노드 중 가장 사전 순으로 뒤에 있는 문자의 노드를 모두 담은 리스트와 현재 문자 길이를 queue에 넣고 빼는 식으로 구현했다.

 

코드는 다음과 같다.

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
"""
import math
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)
n=int(input())
x='a'+input().rstrip()
L=[[] for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)
queue=deque()
queue.append([[1],1])
visited=[0 for i in range(n+1)]
visited[1]=1
ans=x[1]
k='a'
length=1
while queue:
    p,l=queue.popleft()
    if length!=l:
        ans+=k
        length+=1
        k='a'
    X=[]
    for i in p:
        for j in L[i]:
            if not visited[j]:
                if k==x[j]:
                    X.append(j)
                elif k<x[j]:
                    X=[j]
                    k=x[j]
                visited[j]=1
    if X:
        queue.append([X,l+1])
print(ans)​

 

신촌 캠콘 문제.

이걸 왜 콘테스트를 하고 있을 때는 못 풀었을까...

애초에 사전 순으로 정렬이라는 개념에서 그리디를 생각했어야 했다.

사전 순이면 당연히 알파벳 순으로 가장 뒤에 있는 문자로 이동해야 하는데, 일단 문자열의 길이가 가장 긴 게 사전 순에서 맨 뒤라고 생각하고 문제를 풀어서 대회 때는 못 풀었다.

토익으로 인한 멘탈 이슈에 1시간 밖에 못 잔 피지컬 이슈가 크게 작용했던 것 같다.

풀었으면 2회 연속 우승이었을텐데 디펜딩 챔피언이 물로켓이었다는게 드러난 것 같아서 아쉽다.

반복 횟수가 많은 재귀의 경우에는 pypy보다 python이 더 빨라서 pypy에서는 TLE를 받았지만 python에서는 AC를 받았다.