백준 1260 DFS와 BFS

 

 

[TRY 1] 5%에서 틀렸다 나옴 -> 아직도 왜 인지 몰라서 clude한테 물어봄

from collections import deque
import sys


def dfs(v, connection, visited):
    visited[v] = True
    print(v, end = ' ')
    con = []
    
    for i in range(M):
        # print(connection[i][0], end = " ")
        # print(visited[connection[i][0]])
        # print(v, end = "/ ")
        # print( connection[i][1], end = " ")
        # print(visited[connection[i][1]])
        if visited[connection[i][1]] == False and connection[i][0] == v:
            con.append(connection[i][1])
            # print(con)
        if visited[connection[i][0]] == False and connection[i][1] == v:
            con.append(connection[i][0])
            # print(con)
    if len(con) == 0:
        return
    min1 = min_c(con)
    visited[min1] = True
    dfs(min1, connection, visited)
    return

def min_c(con):

    min = 100000000
    for i in range(len(con)):
        if min > con[i]:
            min = con[i]
    return min
    



def bfs(v, connection, visited):
    q = deque([v])

    while q:
        v = q.popleft()
        visited[v] = True
        print(v, end = ' ')

        con = []
        for i in range(M):
            if visited[connection[i][1]] == False and connection[i][0] == v:
                con.append(connection[i][1])
            if visited[connection[i][0]] == False and connection[i][1] == v:
                con.append(connection[i][0])

        if len(con) == 0:
            return
        con.sort()

        for i in range(len(con)):
            q.append(con[i])
        
    return 


N, M, V = map(int, sys.stdin.readline().split())
connection = [list(map(int, sys.stdin.readline().split())) for _ in range(M) ]

visited = [False] * (N+1)
dfs(V, connection, visited)
visited = [False] * (N+1)
print()
bfs(V,connection, visited)

 

 

Clude 답변:

주요 문제점과 예외 케이스, 그리고 개선 방안을 설명드리겠습니다:

1. 그래프 표현 방식: 현재 코드는 간선 리스트를 사용하여 그래프를 표현하고 있습니다. 이 방식은 매번 모든 간선을 순회해야 하므로 비효율적입니다. 인접 리스트나 인접 행렬을 사용하면 성능을 크게 개선할 수 있습니다.
2. DFS 구현: 현재 DFS 구현은 재귀적으로 이루어지고 있지만, 모든 인접 노드를 한 번에 방문하지 않고 최소값만 선택하여 방문합니다. 이로 인해 일부 노드를 방문하지 않을 수 있습니다.
3. BFS 구현: BFS 구현에서도 모든 인접 노드를 즉시 큐에 추가하지 않고, 정렬 후 추가하고 있습니다. 이 방식도 일부 노드를 방문하지 않을 수 있습니다.
4. 방문 처리: BFS에서 노드를 큐에 추가할 때 방문 처리를 해야 합니다. 현재 코드는 큐에서 꺼낼 때 방문 처리를 하고 있어, 중복 방문이 발생할 수 있습니다.
5. 예외 케이스:
   • 연결되지 않은 그래프: 현재 코드는 연결되지 않은 그래프의 경우 모든 노드를 방문하지 못할 수 있습니다.
   • 자기 자신으로의 간선: 현재 코드는 자기 자신으로의 간선을 고려하지 않고 있습니다.
   • 양방향 간선: 입력으로 주어지는 간선이 양방향임을 명시적으로 처리해야 합니다.

 

 

 

[TRY 2] 
우선 답변대로 간선리스트로 된 것을 인접 행렬로 바꿨음. 

하지만  16%에서 탈락!

from collections import deque
import sys


def dfs(v, connection, visited):
    visited[v] = True
    print(v, end = ' ')
    con = []
    
    
    for i in connection[v]:
        if visited[i] == False:
           dfs(i, connection, visited)
    
    return

def min_c(con):

    min = 100000000
    for i in range(len(con)):
        if min > con[i]:
            min = con[i]
    return min
    



def bfs(v, connection, visited):
    q = deque([v])

    while q:
        v = q.popleft()
    
        if visited[v] == False:
            print(v, end = ' ')
            visited[v] = True

        for i in connection[v]:
            if visited[i] == False:
                q.append(i)


        
    return 


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

connection =[[] for _ in range(N+1)]
#그래프 표현 방식 = 인접 행렬
for i in range(M):
    a,b = map(int, sys.stdin.readline().split())
    connection[a].append(b)
    connection[b].append(a)

for i in range(N):
    connection[i].sort()

visited = [False] * (N+1)
dfs(V, connection, visited)
visited = [False] * (N+1)
print()
bfs(V,connection, visited)

 

 

이유를 보니까 sort가 들어가기전에 한번 해서 그런듯하다. 

아니 근데 이해가 안되는게 한번 sort되면 리스트가 바뀌지 않는 것이 아닌가?

이해 안됨.. 그래서 Claude한테 물어보니까 아래처럼 답변함.

 

Claude:

• 한 번만 정렬하는 경우: 처음에 모든 연결 리스트를 한 번만 정렬하면, 각 노드의 인접 노드 리스트는 확실히 오름차순으로 정렬됩니다. 이론적으로는 이것만으로도 충분해 보입니다.
• 매번 정렬하는 경우: 그러나 매번 정렬을 하는 것이 더 안전하고 정확한 결과를 보장하는 이유가 있습니다: a) 입력 오류 방지:
  • 입력 데이터가 예상과 다르게 들어올 수 있습니다. 매번 정렬함으로써 입력 순서에 관계없이 항상 올바른 순서를 보장합니다.
  b) 코드의 일관성:
  • DFS와 BFS 함수를 독립적으로 만들 수 있습니다. 이렇게 하면 전처리 과정(미리 정렬)에 의존하지 않아 함수의 재사용성이 높아집니다.
  c) 동적 그래프 처리:
  • 만약 그래프가 동적으로 변할 수 있는 상황(이 문제에서는 해당되지 않지만)이라면, 매번 정렬하는 것이 안전합니다.
  d) 구현의 단순화:
  • 매번 정렬하면 코드가 더 단순해지고, 실수할 가능성이 줄어듭니다.
• 성능 차이:
  • 대부분의 경우, 노드의 인접 리스트 길이가 크지 않아 매번 정렬하는 것의 성능 저하는 미미합니다.
  • 오히려 캐시 효율 등의 이유로 지역성이 좋은 코드(함수 내에서 모든 처리를 하는)가 더 빠를 수 있습니다.
• 문제 특성:
  • 이 특정 문제에서는 한 번만 정렬해도 충분할 수 있지만, 일반적인 DFS/BFS 구현에서는 매번 정렬하는 것이 더 안전하고 범용적입니다.

봐도 이해 안됨. 왜 그렇게 되는데? 이게 인터프리터 라서 파이썬이 여러 경우에서도 예외처리해줘야하나..? 생각이 들긴했는데 그냥 함수 재사용을 위해 그렇게 하는 걸로 생각하기로 했다. 

 

 

[TRY3 - 최종 코드]

그래서 최종 코드 

 

메모리:115232KB

시간: 148ms

DFS와 BFS 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

300105

118227

70174

38.023%

 

from collections import deque
import sys


def dfs(v, connection, visited):
    visited[v] = True
    print(v, end = ' ')
    con = []
    
    
    for i in sorted(connection[v]):
        if visited[i] == False:
           dfs(i, connection, visited)
    
    return

    



def bfs(v, connection, visited):
    q = deque([v])
    

    while q:
        v = q.popleft()
    
        if visited[v] == False:
            print(v, end = ' ')
            visited[v] = True


        for i in sorted(connection[v]):
            if visited[i] == False:
                q.append(i)


        
    return 


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

connection =[[] for _ in range(N+1)]
#그래프 표현 방식 = 인접 행렬
for i in range(M):
    a,b = map(int, sys.stdin.readline().split())
    connection[a].append(b)
    connection[b].append(a)



visited = [False] * (N+1)
dfs(V, connection, visited)
visited = [False] * (N+1)
print()
bfs(V,connection, visited)