글 읽기 - 혹시 제가 잘못 이해하고 있는건가요?

won7963 3년 전 0

문제 테스트 케이스에 중복 입력이 있다고 해서 간선 중복을 거르는 코드를 붙였는데도 오답처리 되는거 보아하니

혹시 이러한 인풋이 있다고할때

6 8
1 2
1 2
1 2
1 2
1 3
1 4
1 5
1 6

출력은

1 4 2 3 5 6 이 아니라

1 4 2 5 3 6 이 되어야하나요?

첫 노드 방문만 특별하게 하고 나머지는 dfs 순으로 가는게 아니라 쭉 민식이가 정한 룰로 서치하는건가 싶어서요

from sys import stdin
from collections import deque


def mFS(graph):
    que = deque()
    visit = {}
    visit_list = []
    que.append(1)
    while len(que) > 0:
        current_node = que.pop()

        if current_node in visit:
            continue

        visit_list.append(current_node)
        visit[current_node] = True

        connected_node_list = []

        for node in graph[current_node]:
            if node not in visit:
                connected_node_list.append(node)

        num_of_connection = len(connected_node_list)
        
        if num_of_connection == 0:
            continue

        elif num_of_connection % 2 == 1:
            mid_idx = num_of_connection // 2
            mid_ele = connected_node_list[mid_idx]
            connected_node_list = connected_node_list[:mid_idx] + connected_node_list[mid_idx + 1:]
            for idx in range(len(connected_node_list) - 1, -1, -1):
                que.append(connected_node_list[idx])
            que.append(mid_ele)
        else:
            for idx in range(len(connected_node_list[1:]) - 1, -1, -1):
                que.append(connected_node_list[idx + 1])
            que.append(connected_node_list[0])
    return visit_list


N, M = list(map(int, stdin.readline().split()))

graph = {}
for i in range(1, N + 1):
    graph[i] = []

for _ in range(M):
    node01, node02 = list(map(int, stdin.readline().split()))
    if node01 == node02:
        continue
    if node02 not in graph[node01]:
        graph[node01].append(node02)
    if node01 not in graph[node02]:
        graph[node02].append(node01)

for i in range(1, N + 1):
    graph[i].sort()

visit_list = mFS(graph)
return_str = ''

for node in visit_list:
    return_str += str(node) + ' '

print(return_str)

pl0892029 3년 전 1

모든 노드 선택에 대해서 민식우선탐색을 하는 겁니다.

won7963 3년 전 0

답변감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

혹시 제가 잘못 이해하고 있는건가요?

won7963 3년 전 0

pl0892029 3년 전 1

won7963 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말