이번에 풀어본 문제는
백준 1976번 여행 가자 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    static int N,M;
    static int [] parents;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        parents = new int[N + 1];
        for (int i = 0; i <= N; i++) parents[i] = i;
        StringTokenizer st;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 1; j <= N; j++) {
                int next = Integer.parseInt(st.nextToken());
                if(next > 0) {
                    setParent(i,j);
                }
            }
        }

        //여행 경로 입력
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int before = getParent(start);
        int cur = 0;
        String answer = "YES";
        while(st.hasMoreTokens()) {
            int next = Integer.parseInt(st.nextToken());
            cur = getParent(next);
            //두 목적지의 부모가 다르면
            if (before != cur) {
                answer = "NO";
                break;
            }
            before = cur;
        }
        System.out.print(answer);
    }
    static void setParent(int i, int j) {
        int fst = getParent(i);
        int sec = getParent(j);

        //현재 부모가 다를때만
        if(fst != sec) {
            // 작은 수가 부모
            if (fst < sec) parents[sec] = fst;
            else parents[fst] = sec;
        }
    }
    static int getParent(int child) {
        return child == parents[child] ? child : getParent(parents[child]);
    }
}

📝 풀이

N개의 도시들의 연결 여부가 주어질 때, M개의 여행 코스가 이동 가능한 코스라면 YES, 아니라면 NO를 출력하는 문제입니다.
양방향 연결이기 때문에 한 번 연관된 도시는 같은 부모를 가진다고 가정할 수 있을 것 같아 유니온 파인드를 활용해 보았습니다.
입력된 값이 1이라면 연결된 도시이므로, 작은 숫자를 부모로 하여 각 도시의 부모 노드를 찾아가며 그래프를 완성해줍니다.
마지막으로 M개의 여행 경로를 탐색하면서 이전 노드와 부모노드가 다를 경우, 연결되지 않았다고 판단하면 해결할 수 있습니다.

📜 후기

첫 시도에서 그래프 탐색으로 접근했었는데, 최적의 방식이 아닐 것 같다는 생각이 들어 중간에 다시 생각해 보았습니다. 다음부터는 문제를 읽고 빠르게 적합한 알고리즘을 파악할 수 있도록 좀 더 많은 문제를 풀어봐야할 것 같습니다.