13023번: ABCDE(33분)

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

문제 이해 13분 구현 아이디어 3분 구현 17분

풀이

연결된 친구를 찾아가며 간선을 4번 이상 지났을 때 1을 리턴하면 되는 문제이다. 시간 초과가 될 수 있기 때문에 재귀의 종료 조건을 적절히 잡아야 한다. 나는 if(result >= 4) return; 이 문구를 추가했더니 시간 제한 문제를 통과했다.

#include <bits/stdc++.h>

using namespace std;

vector<int> graph[2001];
int check[2001];
int result;

void DFS(int s, int len)
{
    if(result < len) result = len;
    if(result >= 4) return;
    for (int i = 0; i < (int)graph[s].size(); ++i)
    {
        int child = graph[s][i];
        if (check[child] == 0)
        {
            check[child] = 1;
            DFS(child, len + 1);
            check[child] = 0;
        }
    }
}

int main() {
    int N, M;
    scanf("%d %d", &N, &M);

    // 인접 리스트 작성.
    for (int i = 0; i < M; ++i)
    {
        int a, b;
        scanf("%d %d", &a, &b);

        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    for (int i = 0; i < N; ++i)
    {
        result = 0;
        for(int j = 0; j < N; ++j)
            check[j] = 0;
        
        // 시작 정점.
        check[i] = 1;
        DFS(i, 0);
        if (result >= 4)
        {
            printf("1");
            return 0;
        }
    }

    printf("0");
    
    return 0;
}

---

개인적인 감상. 문제 지문 이해에 블로그를 참고했다. 즉, 참고까지 했는데 13분 걸렸다는 뜻이다. 실제 코딩테스트면 이해에만 30분 썼을 듯...