글 읽기 - 제가 푼 방식이 DFS라 할 수 있을까요?

chm4332 1년 전 0

DFS를 오늘 처음 공부해서 문제를 풀어봤는데요,

그냥 2차원 배열 탐색인지, 깊이 우선 탐색인지 잘 모르겠습니다.

방문 순서는 인덱스 기준 0 - 1 - 2 - 4 - 5 (컴퓨터 기준 1-2-3-5-6) 로 나오는데요

뭔가 잘못 알고있는건지... ㅠㅠ

감사합니다

n = int(input())
p = int(input())
graph = [[] for _ in range(n)]
#각 컴퓨터 감염여부 표시 배열
computer = [0 for _ in range(n)]
#양방향 배열 만들기
for _ in range(p):
  start, end = map(int, input().split())
  graph[start - 1].append(end - 1)
  graph[end-1].append(start-1)
  
def dfs(x):
  if computer[x] == 0:
    computer[x] = 1
    for i in range(len(graph[x])):
      dfs(graph[x][i])

dfs(0)
#0번째 컴퓨터 감염 빼주기
cnt = computer.count(1) - 1
print(cnt)
      
    

hhs2003 1년 전 2

DFS 맞습니다.

1 - 2 - 3 - 5 -6 방문 순서 맞지 않나요?

넓이 우선으로 하면

2 5

3 6

순서 일 겁니다.

komjun 1년 전 2

작동은 하지만 조금 비효율적입니다 DFS를 호출하는 시점이 아닌 DFS가 호출된 시점에서 방문검사를 하기때문에 이미 방문한 정점이 계속해서 탐색되는 경우가 발생하고 이를 저격하는 테스트케이스가 존재 한다면 터질수도 있을것같습니다.

예제입력에 대한 구현별 dfs 호출 기록입니다.

DFS1 Call 1
DFS1 Call 2
DFS1 Call 3
DFS1 Call 5
DFS1 Call 6

DFS2 Call 1
DFS2 Call 2
DFS2 Call 1
DFS2 Call 3
DFS2 Call 2
DFS2 Call 5
DFS2 Call 1
DFS2 Call 2
DFS2 Call 6
DFS2 Call 5
DFS2 Call 5

# 이상적인 DFS코드
def dfs1(x):
  computer[x] = 1
  print(f'DFS1 Call {x + 1}')
  for next in graph[x]:
    if computer[next] == 0:
      dfs1(next)

# 질문자 님이 구현하신 코드
def dfs2(x):
  print(f'DFS2 Call {x + 1}')
  if computer[x] == 0:
    computer[x] = 1
    for i in range(len(graph[x])):
      dfs2(graph[x][i])

komjun 1년 전 0

해당 문제에서는 N값이 작아서 문제가 발생하지 않지만 올바른 구현을 알고계시면 좋을것같습니다.

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

문제

문제

출처

ICPC

제가 푼 방식이 DFS라 할 수 있을까요?

chm4332 1년 전 0

hhs2003 1년 전 2

komjun 1년 전 2

komjun 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말