[백준 13023번] ABCDE - 파이썬

 

① 문제 링크

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

13023번: ABCDE

---

② 알고리즘 분류

그래프 이론, 그래프 탐색, 깊이 우선 탐색

---

③ ★문제풀이 Point★

- N(인원수)의 범위가 2000이 최대이므로 방문 표시를 2001개 만들기

-  dfs를 돌리며 조건(5명의 친구 관계가 성립)에 맞는지 확인

---

④ 풀이

이 문제는 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력하는 문제이다.

문제에서 캠프에 있을 수 있는 명수 N가 최대 2000이므로 방문 표시 visited를 2001개 지정해준다.

 친구 관계를 나타내는 리스트 relations에는 각 인덱스 위치가 특정 사람의 번호라고 생각하고 친구 관계 데이터를 넣어준다.

그다음 0부터 N-1 번호까지 친구 관계를 확인하며 재귀함수 dfs(idx, depth)를 이용해 정답이 있는지 판별한다.

재귀함수 dfs(idx, depth)에서 재귀적으로 친구 관계 표시를 수행하되, 문제의 조건에 맞는 친구 관계가 5명 이상 존재한다면   depth = 4 정답을 표시해준다.

---

⑤ 코드

다음 코드는 Python3로 작성하였습니다.

# 13023번 ABCDE

from sys import stdin
input = stdin.readline

# 입력값 받기
n, m = map(int, input().split())
relations = [[] for _ in range(n)]
# 방문 표시
visited = [False] * 2001
# 정답 변수 생성
ans = False
# 친구 관계 입력받기
for i in range(m):
    a, b = map(int, input().split())
    # 친구 관계 등록
    relations[a].append(b)
    relations[b].append(a)

# dfs 이용
def dfs(idx, depth):
    global ans
    visited[idx] = True
    # 친구 관계가 4번 이상 연결되어 있다면
    if depth == 4:
        # 정답 표시 후 리턴
        ans = True
        return
    # 친구 관계가 존재하는지 확인
    for i in relations[idx]:
        # 아직 방문하지 않았다면
        if not visited[i]:
            # 방문 표시
            visited[i] = True
            # 재귀적으로 수행
            dfs(i, depth + 1)
            # 방문 표시 해제
            visited[i] = False

# 0번부터 N-1번까지 확인하며
for i in range(n):
    # 친구 관계 탐색
    dfs(i, 0)
    # 현재 방문 표시 해제
    visited[i] = False
    # 친구 관계가 존재한다면
    if ans:
        # 탈출
        break
# 정답이 있다면 1 출력
if ans:
    print(1)
# 정답이 없다면 0 출력
else:
    print(0)

 

13023 ABCDE 파이썬 채점 결과

---

 

백준 13023번 ABCDE