코딩테스트 대비 문제 풀기

백준(13023) : ABCDE

0. 간단한 설명

• 관련 알고리즘 : dfs(깊이 우선 탐색)

• 코드 풀이

  • 아래와 같이 3단계의 함수 구성으로 구분하여 코드 생성
  • dfs와 check 함수의 흐름에 대해 이해가 안되는 부분은 실제 코드 돌아가는 모양에 대해 예시를 직접 풀어 써보고 이해하려고 했음

1. 코드 풀이

1) 함수 정의 : 친구관계 입력받아 자료 생성

def makerels(n, m):
    relations = [[] for _ in range(n)]
    visited = [0] * n
    for i in range(m):
        a, b = map(int, input().split())
        relations[a].append(b)
        relations[b].append(a)
    return relations, visited

2) 함수 정의 : dfs 이용

def dfs(idx, depth):
    global relations, visited

    if depth == 4:
        print(1)
        exit()

    for i in relations[idx]:
        if visited[i] == 0:
            visited[i] = 1
            dfs(i, depth+1)
            visited[i] = 0

3) 함수 정의 : 전체 인원에 대해 관계 탐색

def check(n):
    for j in range(n):
        visited[j] = 1
        dfs(j,0)
        visited[j] = 0
    print(0)

4) 전체 인원수 및 친구 관계 수 입력받아 함수 실행시키기

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

relations, visited = makerels(N, M)

check(N)

2. 예시를 통한 코드 이해

1) 친구 관계 예시

2) 구현 코드 관련 번호 붙이기

3) 예시 관계에 관한 실행 코드들을 한 줄 씩 번호와 매칭하여 나열
→ 재귀 호출 시, 코드가 한 단계씩 깊이 들어가는 것으로 생각하여 안쪽 네모박스로 코드를 담아두었음.