[BOJ] 13023. ABCDE (python / java)

✏️ 문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.
오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.
A는 B와 친구다.B는 C와 친구다.C는 D와 친구다.D는 E와 친구다.
위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

 

🤖 알고리즘

#그래프  #백트래킹

 

🤯 풀이 방법

친구 관계를 가진 A, B, C, D, E가 있냐는 말인데, 그냥 그래프를 순회해서 다섯 단계까지 갈 수 있냐는 뜻이다.

자바로 생각할 때는 금방 풀어서 구현했는데 몇 주 뒤에 파이썬으로 하려니 시간초과 나고 난리도 아니었다.

일단 그래프 관계를 리스트로 만들고, 함수를 만들어서 0부터 순서대로 시작점으로 설정하여 다섯 단계까지 갈 수 있는지 확인한다. 하나라도 경우가 존재하는 걸 확인하면 그 뒤로는 굳이 확인할 필요가 없다.

재귀 함수를 돈 후 visited를 false로 설정해주지 않으면 시간 초과가 나는데 어디서 그렇게 큰 차이가 나는지는 잘 모르겠다 ㅠ

 

# [BOJ] <G5> 13023. ABCDE

import sys
input = sys.stdin.readline


def relate(i, r):
    """
    5명까지 갈 수 있는 경우가 잇는지 찾는 함수
    :param i: 현재 순회하고 있는 인덱스
    :param r: 현재 몇 명까지 카운트했는지
    :return: 가능한 경우를 찾으면 종료
    """
    global ans

    if r == 5:
        ans = 1
        return

    v[i] = 1
    for j in R[i]:
        if v[j] == 0:
            relate(j, r + 1)
    v[i] = 0


N, M = map(int, input().split())
R = [[] for _ in range(N)]

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

ans = 0

for i in range(N):
    v = [0] * N
    relate(i, 1)
    if ans == 1:
        break

print(ans)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int M;
    static int ans;
    static ArrayList<Integer>[] friends;
    static boolean[] visited;

    static void search(int start, int cnt) {
        if (cnt == 5) {
            ans = 1;
            return;
        }

        visited[start] = true;
        for (int s : friends[start]) {
            if (!visited[s]) {
                search(s, cnt + 1);
            }
        }
        visited[start] = false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());   // 사람의 수
        M = Integer.parseInt(st.nextToken());   // 친구 관계의 수


        friends = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            friends[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            friends[a].add(b);
            friends[b].add(a);
        }

        ans = 0;
        for (int i = 0; i < N; i++) {
            if (ans == 1) break;
            visited = new boolean[N];
            search(i, 1);
        }
        System.out.println(ans);

    }
}

 

 

13023번: ABCDE