글 읽기 - 1260 문제 반례 및 오류 수정 부탁드립니다!

wwlee94 4년 전 0

예제는 모두 잘 돌아가는데 다른 테스트케이스에서 틀린것 같습니다.

제 생각으로는 dfs는 문제가 전혀 없는거 같은데 bfs에서 문제가 나는듯합니다.

코드에서 수정할 부분이나 반례, 오류를 알려주시면 감사드립니다.

아래 사진은 bfs 출력 과정입니다.

import sys

input_s = lambda: sys.stdin.readline()

N, M, start = map(int,input_s().split())
abj = [list(map(int,input_s().split())) for i in range(M)]
# 뒤에 정렬 후 앞 정렬 -> 최종적으론 x[0]으로 오름차순 정렬 (같으면 뒤 기준 오름차순)
abj.sort(key=lambda x: x[1])
abj.sort(key=lambda x: x[0])

tree = {}
visit_dfs = []

visit_bfs = []
queue_bfs = []

def init():
    for i in range(1,N+1):
        tree[i] = []
    for i in range(M):
        if abj[i][1] not in tree[abj[i][0]]:
            tree[abj[i][0]].append(abj[i][1])
        if abj[i][0] not in tree[abj[i][1]]:
            tree[abj[i][1]].append(abj[i][0])
# 재귀 형식으로 visit_dfs에 방문한 노드 stack을 사용하여 출력
def search_dfs(tree,start):

    visit_dfs.append(start)

    for i in tree[start]:
        if i not in visit_dfs:
            search_dfs(tree,i)

def search_bfs(tree,start):

    queue_bfs.append(start)

    while queue_bfs:
        # print("visit_bfs " + str(visit_bfs))
        # print("queue_bfs " + str(queue_bfs))
        # 시작위치 변경 후 제거
        start = queue_bfs.pop(0)
        # 추가
        visit_bfs.append(start)
        for j in tree[start]:
            if j not in visit_bfs and j not in queue_bfs:
                queue_bfs.append(j)


def show(list):
    for i in list:
        print(i,end=" ")


init()
# print(tree)
search_dfs(tree, start)
search_bfs(tree, start)
show(visit_dfs)
print()
show(visit_bfs)

wwlee94 4년 전 0

초기 오름차순 정렬이 잘못되었습니다.

문제 해결 했습니다.

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

문제

문제

출처

ICPC

1260 문제 반례 및 오류 수정 부탁드립니다!

wwlee94 4년 전 0

wwlee94 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말