[백준/13023] ABCDE

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

 

Difficulty : Gold 5

 

Status : Solved

 

Time : ?? : ?? : ??

 

---

 

문제 설명

 

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을 출력한다.

 

입력 예시

 

5 4
0 1
1 2
2 3
3 4

 

출력 예시

 

1

 

 

---

 

풀이

 

간단한 dfs + 백트래킹 문제. 이미 방문한 지점을 제외하고 거리가 5가 될때까지 방문을 시행하는 모든 경우를 고려하면 된다. N = 2000, M = 2000인 작은 숫자이므로 가능한 기예라 볼 수 있겠다.

 

풀이 코드 (Python)

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
friend = [[] for _ in range(N)]
for _ in range(M):
  a, b = map(int, input().split())
  friend[a].append(b)
  friend[b].append(a)

visited = [False] * N
answer = 0

def dfs(node, depth):
  if depth == 4:
    return True
  for nxt in friend[node]:
    if not visited[nxt]:
      visited[nxt] = True
      if dfs(nxt, depth + 1):
        return True
      visited[nxt] = False


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

 

풀이 코드 (Go)

package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	visited []bool
	graph   [][]int
)

func dfs(node, depth int) bool {
	if depth == 4 {
		return true
	}
	for _, next := range graph[node] {
		if !visited[next] {
			visited[next] = true
			if dfs(next, depth+1) {
				return true
			}
			visited[next] = false
		}
	}
	return false
}

func main() {
	var reader *bufio.Reader = bufio.NewReader(os.Stdin)
	var N, M, a, b int

	fmt.Fscanln(reader, &N, &M)
	visited = make([]bool, N)
	graph = make([][]int, N)
	for i := 0; i < M; i++ {
		fmt.Fscanln(reader, &a, &b)
		graph[a] = append(graph[a], b)
		graph[b] = append(graph[b], a)
	}
	
	for i := 0; i < N; i++ {
		visited[i] = true
		if dfs(i, 0) {
			fmt.Println(1)
			return
		}
		visited[i] = false
	}
	fmt.Println(0)
}

 

풀이 완료!