백준 13265 색칠하기

백준 13265 색칠하기

---

• 이번 문제는 DFS 를 활용한 색칠 가능 여부를 묻는 문제였다. 사실 이렇게 오래 걸릴게 아니었던 것 같은데 지금까지 상하좌우로 좌표상에서 움직이는 dfs 에 너무 익숙해져버린
  나머지 너무 오래걸렸다.
• DFS 를 재귀를 통해 푸는 풀이가 많은데 난 아직 큐를 활용하는 방식을 고정해 사용하고 있다. 이 방식이 좀 더 귀찮고 코드 길이도 길고 번거로운 것 같기도 해 재귀를 통한 방식을 새로 익히는 것도 고려
  해봐야겠다.
• 자바에서 벡터를 이번에 처음 사용해 보았는데, 아직까진 그냥 list 와 큰 차이는 모르겠지만 자주 사용해 보아야겠다.
• list 를 재귀문 밖에 사용해서 지금까지 계속 틀렸다.

for (int i = 0; i < t; i++) {
            int visited[] = new int[1002];
            int color[] = new int[1002];
            Vector<Vector<Integer>> list = new Vector<Vector<Integer>>();
            StringTokenizer st= new StringTokenizer(scanner.nextLine());

            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            for (int j = 0; j <= n; j++) {
                list.add(new Vector<Integer>());
            }
            for (int j = 0; j < m; j++) {
                st = new StringTokenizer(scanner.nextLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                list.get(from).add(to);
                list.get(to).add(from);
            }
            boolean answer = true;

            Queue<Integer> q = new LinkedList<>();
            for (int j = 1; j <= n; j++) {
                if (visited[j] == 0) {
                    color[j] = 1; visited[j] = 1;
                    q.add(j);
                    while (!q.isEmpty()) {
                        int cur = q.peek(); q.remove();
                        for (int k = 0; k < list.get(cur).size(); k++) {
                            if (color[cur] == color[list.get(cur).get(k)]) {
                                answer = false;
                            }
                            if (visited[list.get(cur).get(k)] == 1 ) continue;
                            color[list.get(cur).get(k)] = 3 - color[cur];
                            q.add(list.get(cur).get(k));
                            visited[list.get(cur).get(k)] = 1;
                        }
                    }
                }
            }
            if (!answer) {
                System.out.println("impossible");
            } else {
                System.out.println("possible");
            }
        }

• 각 동그라미가 인접해 있는 점을 vector 로 관리해 현재 cur 동그라미와 다른 색을 칠해주다, 만약 이미 칠해진 동그라미가 cur와 같은 색이라면 터뜨려 주었다.