BOJ(ABCDE)

작성일 | In

ABCDE 문제 (그래프)(1번)

  • ABCDE

  • 전형적인 완전탐색 문제.
  • 예제의 A,B,C,D,E가 노드, 친구관계를 간선으로. 양방향 그래프로 생각해보자.

  • 5명의 이어진 친구관계가 성립하면, 즉 존재하면 1을 출력 아닐 경우 0

  • DFS를 돌면서, Depth가 깊어질 때마다 count(초기값 0) 4가 되면 return 1을 하면 되지 않을까?

  • 마치 SWE의 그래프의 경로와 비슷하다.

  • 이 문제 1시간 넘게 고민하고 틀렸는데, 왜 틀렸는지 정확한 원인을 못찾았다. 시간초과가 계속 떴다.
import sys
input = sys.stdin.readline


def DFS(s, depth):
    global result
    visited[s] = True
    for i in range(N):
        if arr[s][i] and not visited[i]:
            if depth == 5:
                result = 1
                return
            DFS(i, depth+1)
    visited[s] = False
    return


N, M = map(int, input().split())
arr = [[0]*(N+1) for _ in range(N+1)]

for i in range(1, M+1):
    a, b = map(int, input().split())
    arr[a][b] = 1
    arr[b][a] = 1  # 무방향 그래프이므로
visited = [False]*(N+1)
result = 0
for i in range(N):
    visited[i] = True
    DFS(i, 1)
    if result == 1:
        break
    visited[i] = False
print(result)
  • 아마도 초기 리스트를 만들 때, 나는 2차원 리스를 만들어서 돌렸는데, 다른 분들은 대개 인접리스트를 활용하셨다.

  • 이 기회에 인접리스트의 구현 방법을 익혀두자.

  • 인접리스트를 알아가려고 이렇게 고생했나보다 ..
def DFS(s, depth):
    global result
    if depth >= 4:
        result = 1
        return
    for i in arr[s]:
        if not visited[i]:
            visited[i] = True
            DFS(i, depth+1)
            visited[i] = False


N, M = map(int, input().split())
visited = [False] * N
arr = [[] for _ in range(N)]
result = 0
for _ in range(M):
    a, b = map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)


for i in range(N):
    visited[i] = True
    DFS(i, 0)
    if result == 1:
        break
    visited[i] = False
print(result)

참고자료 codeplus

0%