글 읽기 - java/ 게시판 반례도 다 넣고 FAQ도 읽었는데 틀려서 답답합니다 . . .

sally3605 3년 전 0

0: 방문 한 적 없는 노드

1: 팀1에 소속

2: 팀2에 소속

되게끔 로직을 짰다고 생각하고, 반례 및 테케들 다 통과되는데 .. 어느부분이 문제인지 감이 안잡힙니다.

코드 조언도 좋으니 고수님들의 지혜로 ,, 부탁드립니다

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 class RC {
        int row;
        int col;
        RC(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    static int K, V, E;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        K = stoi(br.readLine());


        Loop: for (int i = 0; i < K ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            V = stoi(st.nextToken());
            E = stoi(st.nextToken());

            //graph의 node별 연결 점 저장
            ArrayList<Integer>[] graph = new ArrayList[V+1];
            int[] team = new int[V+1];
            List<RC> lines = new ArrayList<>();
            for (int j = 0; j < graph.length ; j++) {
                graph[j] = new ArrayList<>();
            }
            for (int j = 0; j < E ; j++) {
                st = new StringTokenizer(br.readLine(), " ");
                int d1 = stoi(st.nextToken());
                int d2 = stoi(st.nextToken());
                lines.add(new RC(d1, d2));
                graph[d1].add(d2);
                graph[d2].add(d1);

            }


            for (int j = 1; j <= V ; j++) {
            //j의 팀이 아직 정해지지 않은 경우
                if (team[j] == 0) {
                        for (int k = 0; k < graph[j].size(); k++) {
                            team[j] = 1;
                            team[graph[j].get(k)] = 2;
                        }
                    } 
                // j의 팀이 정해져있는 경우
                else {
                        for (int k = 0; k < graph[j].size() ; k++) {
                            //j의 연결점 중 같은 팀이 있는 경우 (이분 탐색에 위배)
                            if (team[graph[j].get(k)] == team[j]) {
                                sb.append("NO\n");
                                continue Loop;
                            } 
                            //아직 팀 소속이 안정해진 경우: j와 반대편으로 배치
                            else if (team[graph[j].get(k)] == 0)
                                team[graph[j].get(k)] = (team[j] == 1)? 2:1;
                        }
                    }


            }
            //노드별 체크
            for (int j = 1 ; j <= V ; j++) {
                for (int k = 0; k < graph[j].size() ; k++) {
                    //연결되어있는 노드끼리 같은 팀 배치 시 위배 --> no 출력 및 다음 TC 진행
                    if (team[graph[j].get(k)] == team[j]) {
                        sb.append("NO\n");
                        continue Loop;
                    }
                }
            }
            //for문 모두 통과한 경우 = 이분 탐색 잘 되었다는 뜻이므로 yes 출력
        sb.append("YES\n");
        }
        System.out.println(sb);
    }

    public static int stoi(String str) {
        return Integer.parseInt(str);
    }
}