백준 13023 ABCDE 파이썬 풀이, 반례

난이도 : 골드5

풀이일 : 2404151

https://www.acmicpc.net/problem/13023

13023번: ABCDE

---

문제 캡쳐

---

문제 이해

 

처음에는 싸이클을 이루지 않는 일방향 친구 관계를 찾으라는 문제라고 이해했다가, 이상해서 예시를 그려보았다.

문제에 그림도 같이 나와있으면 더 이해하기 쉬웠을텐데 아쉽다.

---

아이디어

• 한 사람부터 시작해 이미 지나온 사람을 제외하고 DFS 탐색으로 깊이 5까지 도달할 수 있는 경우가 있는지 탐색하자.

---

전체 풀이코드

import sys

# 한 숫자에서 다섯 번 DFS 호출이 가능한지 확인
def DFS(n, depth):
    visited[n] = True  # 방문표시
    if depth == 5:
        return 1  # 문제 조건 충족 종료
    # 연결된 친구들에 대해 이전에 확인하지 않았다면 DFS 호출
    for friend in friends[n]:
        if not visited[friend]:
            if DFS(friend, depth + 1):
                return 1  # 문제 조건 충족 전달
            visited[friend] = False  # 방문 초기화
    visited[n] = False  # 방문 초기화
    return 0

N, M = map(int, sys.stdin.readline().split())
friends = [[] for _ in range(N)]  # 친구관계 저장
visited = [False] * N

for _ in range(M):  # 친구관계 입력 받기
    a, b = map(int, sys.stdin.readline().split())
    friends[a].append(b)
    friends[b].append(a)

for i in range(N):
    if DFS(i, 1):  # 문제 조건 충족 시
        print(1)
        break
else:
    print(0)  # 문제 조건 미충족 시

---

세부 풀이코드

# 입력 처리
N, M = map(int, sys.stdin.readline().split())
friends = [[] for _ in range(N)]  # 친구관계 저장
visited = [False] * N

for _ in range(M):  # 친구관계 입력 받기
    a, b = map(int, sys.stdin.readline().split())
    friends[a].append(b)
    friends[b].append(a)

• 입력된 정보를 처리하는 부분의 코드이다.
• friends 배열은 이차원 배열로, 각 인덱스가 의미하는 사람과 친구관계인 사람의 정보를 저장한다.
• visited 배열은 향후 DFS 탐색 시, 매 번 생성해서 메모리를 낭비하지 않기 위해 먼저 생성해주었다.
• for 반복문 동안 친구 관계를 입력받고, 양방향으로 기록해준다.

 

# DFS 탐색 및 종료 조건 관리
for i in range(N):
    if DFS(i, 1):  # 문제 조건 충족 시
        print(1)
        break
else:
    print(0)  # 문제 조건 미충족 시

• 각 인덱스를 넣어 DFS 탐색을 시작한다.
• 만약, 탐색 결과가 1이 반환된다면, 1을 출력하고 반복문을 종료한다.
• 반복문이 끝날 때까지 조건을 만족해 중단되는 경우가 없었다면, 0을 출력한다.

 

# 한 숫자에서 다섯 번 DFS 호출이 가능한지 확인
def DFS(n, depth):
    visited[n] = True  # 방문표시
    if depth == 5:
        return 1  # 문제 조건 충족 종료
    # 연결된 친구들에 대해 이전에 확인하지 않았다면 DFS 호출
    for friend in friends[n]:
        if not visited[friend]:
            if DFS(friend, depth + 1):
                return 1  # 문제 조건 충족 전달
            visited[friend] = False  # 방문 초기화
    visited[n] = False  # 방문 초기화
    return 0

• DFS 함수 부분의 코드다.
• 맨 처음, 현재 숫자 방문을 표시해주고, 종료 직전에 현재 숫자의 방문을 초기화한다.
• 만약, depth가 5라면, 문제의 조건을 충족하므로 1을 반환하며 종료한다.
• for 반복문 : 현재 사람과 연결된 친구들에 대해서, 이전에 방문한 적이 없다면, DFS 함수에 depth + 1 하여 재귀 호출한다.
• DFS 재귀 탐색이 끝나면, 해당 방문을 다시 초기화해준다. 이 부분은 반례 때문에 추가되었다.
• 마지막까지 종료되지 않은 경우가 없었다면, 0을 반환하며 종료한다.

---

반례

입력	출력
5 6 0 1 1 4 1 2 1 3 2 4 3 4	1

 

반례의 출처는 아래와 같습니다.

https://www.acmicpc.net/board/view/130285

글 읽기 - 반례 찾아주세요...

---

느낀점

• 어제는 골드 문제를 실패해서 자바로 실버 문제를 풀었는데, 오늘도 겨우겨우 문제를 풀어낸 것 같다. 초반에 문제를 잘못 이해하니까 계속 왜 틀리는지 알수가 없어서 헤맸다.