백준31476 :blob_twintail_thinking: [python]

문제링크 https://www.acmicpc.net/problem/31476

 

문제

이해를 돕기 위해 아래 예제를 준비하였다. 왼쪽이 양갈래 블롭들이 탐색하는 방법, 오른쪽이 포니테일 블롭들이 탐색하는 방법이다.

 

문제 풀이

문제 풀이 아이디어

1. 트리의 깊이를 입력받고 완전이진트리를 구성

2. N개의 파손된 길의 정보를 입력받고 노드의 연결관계 끊기

3. 포니테일 블롭은 dfs로 트리를 탐색

4. 양갈래 블롭은 bfs로 트리를 탐색

5. 탐색을 완료하는데 걸리는 시간비교후 답 출력.

 

구현

1. 입력처리

def main():
    D,N,U,T=map(int,input().split())
    if D==1:
        print(':blob_twintail_thinking:')
        return
    P=set(tuple(map(int, input().split())) for _ in range(N))

 

 

2. 완전이진트리 구성하는 함수 구현

def create_tree(D,P):
    gr=defaultdict(list)
    nodes=2**D-1 #완전이진트리는 노드의 개수를 (2^deeps)-1개를 가진다.
    for i in range(1,nodes+1):
        left=2*i
        right=2*i+1
        if left<=nodes and (i,left) not in P: #끊어진 관계가 아니면 연결관계 추가
            gr[i].append(left)
        if right<=nodes and (i,right)not in P: #끊어진 관계가 아니면 연결관계 추가
            gr[i].append(right)
    return gr

 

 

3. 양갈래 블롭들의 탐색방식인 bfs함수 구현

def bfs(gr,D,U,T):
    V=[INF]*2**D # 각 노드의 탐색 시간을 저장할 visit배열
    q=deque([[1,U]])
    V[1]=0
    j=0 # 탐색하는 데에 가장 오래 걸린 팀의 탐색 시간을 저장할 변수
    while q:
        node,move_t=q.popleft()
        if not gr[node]:#더이상 연결관계가 없는것은 탐색이 완료되었다는 것 이므로 결과값 갱신
            j=max(V[node],j)
        for next_n in gr[node]:
            if V[next_n]!=INF:continue # 방문한노드는 pass
            if len(gr[node])==2: #길이 나누어져 있으면 세력나누기
                q.append([next_n,move_t+T])
                V[next_n]=move_t+T+V[node]
            else: #길이 나누어져 있지 않으면 일반 처리
                q.append([next_n,move_t])
                V[next_n]=move_t+V[node]
    return j

 

 

4.포니테일 블롭들의 탐색방식인 dfs함수 구현

def dfs_path(graph):
    global last_visited_node
    path = []
    visited = set()
    last_visited_node=1 #마지막으로 탐색한 노드 
    def dfs(node):
        global last_visited_node
        visited.add(node)
        path.append(node) #탐색 노드 기록
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                last_visited_node=neighbor
                dfs(neighbor)
                path.append(node) #탐색 노드 기록
    dfs(1)
    for i in range(len(path)-1,-1,-1): #탐색후 다시 돌아오는 기록을 제거
    	if path[i]!=last_visited_node:
    		path.pop()
    	else:
    		break
    return len(path)-1 #첫번째에 시작노드가 포함되어있으므로 기록의 노드개수-1

 

 

5.결과 비교후 답 출력

def main():
	gr=create_tree(D,P)
    tb=bfs(gr,D,U,T)
    pb=dfs_path(gr)*U
    if pb==tb:
    	print(':blob_twintail_thinking:')
    	return
    print(':blob_twintail_aww:'if tb<pb else ':blob_twintail_sad:')

 

 

전체 코드

from collections import deque,defaultdict
input=open(0).readline
INF=float('inf')
def create_tree(D,P):
    gr=defaultdict(list)
    nodes=2**D-1
    for i in range(1,nodes+1):
        left=2*i
        right=2*i+1
        if left<=nodes and (i,left) not in P:
            gr[i].append(left)
        if right<=nodes and (i,right)not in P:
            gr[i].append(right)
    return gr
def bfs(gr,D,U,T):
    V=[INF]*2**D
    q=deque([[1,U]])
    V[1]=0
    j=0
    while q:
        node,move_t=q.popleft()
        if not gr[node]:
            j=max(V[node],j)
        for next_n in gr[node]:
            if V[next_n]!=INF:continue
            if len(gr[node])==2:
                q.append([next_n,move_t+T])
                V[next_n]=move_t+T+V[node]
            else:
                q.append([next_n,move_t])
                V[next_n]=move_t+V[node]
    return j
def dfs_path(graph):
    global last_visited_node
    path = []
    visited = set()
    last_visited_node=1
    def dfs(node):
        global last_visited_node
        visited.add(node)
        path.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                last_visited_node=neighbor
                dfs(neighbor)
                path.append(node)
    dfs(1)
    for i in range(len(path)-1,-1,-1):
    	if path[i]!=last_visited_node:
    		path.pop()
    	else:
    		break
    return len(path)-1

def main():
    D,N,U,T=map(int,input().split())
    if D==1:
        print(':blob_twintail_thinking:')
        return
    P=set(tuple(map(int, input().split())) for _ in range(N))
    gr=create_tree(D,P)
    tb=bfs(gr,D,U,T)
    pb=dfs_path(gr)*U
    if pb==tb:
    	print(':blob_twintail_thinking:')
    	return
    print(':blob_twintail_aww:'if tb<pb else ':blob_twintail_sad:')
main()

 

회고

그렇게 어렵지는 않은 문제이었다. 약간의 bfs,dfs응용을 하느라 구현에서 시간을 좀 썼습니다. 그리고 엣지케이스를 고려를 안해서 몇번 틀리고 수정해서 정답을 맞았습니다.

 

문제 태그:

 #bfs #dfs #그래프 이론 #그래프 탐색 #트리