[BOJ 애드혹] 스피카 21316.JAVA

문제 링크 : https://www.acmicpc.net/problem/21316

21316번: 스피카

문제 풀이

1. 각 별들의 이동 경로(양방향)를 기록한다.
2. 스피카 별의 주변의 별들의 특성대로 이동 경로의 개수를 확인하여 스피카를 찾는다.
   1. 이동 경로가 3개인 별
   2. 이동 경로가 2개인 별
   3. 이동 경로가 1개인 별

아래와 같이 소스를 공유합니다.

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 {
    public static int ans = 0;
    public static List<List<Integer>> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String str = "";

        for(int i = 0; i <= 12; i++) list.add(new ArrayList<>());
        while(!(str = br.readLine()).equals("")) {
            StringTokenizer st = new StringTokenizer(str, " ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            list.get(s).add(e);
            list.get(e).add(s);
        }

        for(int i = 0; i < list.size(); i++) {
            boolean first = false, second = false, third = false;
            if(list.get(i).size() == 3) {
                for(int j = 0; j < 3; j++) {
                    int side = list.get(list.get(i).get(j)).size();
                    
                    if(!third && side == 3) third = true;
                    if(!second && side == 2) second = true;
                    if(!first && side == 1) first = true;
                }
            }

            if(third && second && first) ans = i;
        }

        System.out.println(ans);
    }
}

---

처음 문제를 접했을 때 예제 입력을 보고 단방향으로 진행되는 문제라고 생각했다.

나에게 오는 별이 2개, 나가는 별이 1개를 체크하는 로직을 구현했으나 틀렸다.

최근에 올라온 문제라서 다른 사람들이 구현한 로직을 볼 수 없었다.

그래서 스터디 원에게 물어보니 이 문제는 단방향이 아닌 양방향이라는 힌트를 주었다.

양방향이라는 말을 듣고 다시 문제를 풀어 해답을 찾았다.

이 문제에는 방향에 대한 명확한 제시가 없다.

당연히 단방향이 아니면 양방향으로 문제를 풀어봤어야 했는데 판단을 잘못해 문제를 한 번에 풀지 못하였다.