백준 13023번 ABCDE

1. 문제 설명

문제링크

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

 

• 입력
  • 첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.
  • 둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구
  • 관계가 두 번 이상 주어지는 경우는 없다.
• 출력
  • 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

2. 코드

import sys

input = sys.stdin.readline

def DFS(start, cnt):
    # 만약에 start를 통해서 e로 갈수 있는 즉 친구가 4명이 되는지 판별
    if cnt == 4:
        # 출력
        print(1)

        # 테스트케이스 종료
        exit()
    # graph[start]를 통해 추가된 값으로 이동
    for i in graph[start]:
        # 방문 하지 않았다면
        if not visit[i]:
            # 방문 처리후
            visit[i] = True

            # DFS 시작
            DFS(i, cnt + 1)

            # 방문 처리 해제
            visit[i] = False
# n, m 입력
n, m = map(int, input().split())

# 2차원 그래프
graph = [[] for _ in range(n)]

# 방문 요소를 나타내는 리스트
visit = [False] * n

# m개의 친구 요소 입력 받기
for _ in range(m):
    # a 와 b가 친구 임을 나타내는 입력 값
    a, b = map(int, input().split())
    # a 와 b 가 친구이므로 graph[a] 에 b 값 추가하기
    graph[a].append(b)
    # 반대로 a 와 b 가 친구이므로 graph[b] 에서도 a 로 이동이 가능해야 하므로 a 값 추가하기
    graph[b].append(a)


# 문제에서 주어지는 A를 통해서 E로 갈수 있는지 없는지를 알기 위한 반복문.
for i in range(n):
    # 방문 처리
    visit[i] = True

    # DFS 시작
    DFS(i, 0)

    # 방문 처리 해제
    visit[i] = False
# 출력
print(0)

3. 회고

Q. 문제를 보고 든 생각

• 단순하게 DFS를 이용해서 A 라는 값을 통해 E값을 도출 해낼수 있는지를 물어보는 문제라고 생각되었다.
• 하지만 단순한 DFS 보단 백트래킹을 이용해야 풀리는 문제 였고 백트래킹을 공부하고 문제를 접근 하게 되면서 풀 수있게 된 문제였다.

4. 아쉬운 점 혹은 고쳐야 할점

조금더 좋은 풀이가 있다면 댓글로 알려주세요