글 읽기 - 13023번 파이썬 반례좀 부탁드립니다

slide97 1년 전 0

기본적으로 DFS 를 stack으로 구현했고, depth를 구하기 위해 flag를 두어 사용하지 않은 친구관계가 있으면 depth를 1 늘려주는 방식으로 풀었습니다.

재귀방식으로 풀어야 맞을수 있을까요? 조언 부탁드립니다.

import sys
from collections import deque

def input():
    return sys.stdin.readline().rstrip()

n, m = map(int, input().split())
graph = [[] for _ in range(n) for _ in range(n)]

for i in range(m):
    v, e = map(int, input().split())
    graph[v].append(e)
    graph[e].append(v)

answer = 0

for i in range(n):
    depth = 1
    stack = deque([i])
    visited = [False for _ in range(n)]
    while len(stack):

        flag = False
        node = stack.pop()
        if visited[node]:
            continue
        if depth == 5:
            answer = 1
            break
        visited[node] = True

        for j in graph[node]:
            if not visited[j]:
                flag = True
                stack.append(j)
        if flag:
            depth += 1

    if answer == 1:
        break

print(answer)

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

문제

문제

출처

ICPC

13023번 파이썬 반례좀 부탁드립니다

slide97 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말