[자바] 백준 2653 - 안정된 집단 (java)

목차

문제 : boj2653

 

 

필요 알고리즘

• 직관(?), 그래프 이론
  
  • 어찌보면 그냥 구현 문제이긴 한데, 좀 헷갈릴 수도 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  서로 싫어하는 사람들은 빼고, 그냥 서로 좋아하는 사람들끼리 집단을 만든다고 생각해보자. 이 때 문제에서 제시된 바에 따라 논리적으로 맞는지만 확인해주면 된다. 내 로직은 다음과 같다. 이하 로직대로 구현해주면 된다.

 

1. 1부터 N까지 확인하다가 아직 방문된 적 없는 가장 작은 X번을 선택한다.

2. X가 좋아하는 사람들을 그룹에 넣는다.

3. 이 때, X번이 좋아하는 사람중에 이미 방문된 적이 있는 사람이 있다면, 논리적으로 맞지 않으므로 0을 출력하고 종료한다. (X번을 싫어하는 사람이 있는 그룹에 X가 좋아하는 사람이 들어갈 수 없다.)

4. 그룹원이 정해졌다면, 그룹원들끼리 서로가 서로를 전부 좋아하는지 확인한다. 아니라면 0을 출력하고 끝낸다.

5. 그룹원이 총 한명이라면 0을 출력하면 종료한다.

6. 다시 '1'을 진행한다.

 

 

  예를들어 문제에 제시된 '그림 1'에서 1과 4가 서로 싫어한다고 생각해보자. 이 경우 위 로직대로 진행하다보면, X가 4일 때 '2'에서 5번이 그룹에 들어가는데 이미 방문된 적 있으므로 '3'에 의해 종료된다.

 

 

  이번엔 4와 5가 서로 싫어한다고 해보자. 이 경우 X=1일 때 4번과 5번이 그룹에 들어가지만, '4'에 의해 종료된다... 여야 하는데 제출해보니 '4'를 체크하지 않아도 통과되는걸 확인했다. 채점 테스트케이스가 빈약한 것 같다. '4'의 과정은 논리상 반드시 필요하다. 채점이 틀린경우로, 아무튼 '4' 로직도 필요하다.

    

 

코드 : github

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        boolean[][] arr = new boolean[n+1][n+1];
        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                arr[i][j] = st.nextToken().charAt(0) == '0';
            }
        }

        boolean[] v = new boolean[n+1];
        StringBuilder sb = new StringBuilder();
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (v[i]) continue;
            v[i] = true;

            List<Integer> tmp = new ArrayList<>();
            tmp.add(i);
            for (int j = 1; j <= n; j++) {
                if (i == j || !arr[i][j]) continue;
                if (v[j]) {
                    end();
                    return;
                }
                v[j] = true;
                tmp.add(j);
            }

            if (tmp.size() == 1) {
                end();
                return;
            }

            for (int cur1 : tmp) {
                for (int cur2 : tmp) {
                    if (!arr[cur1][cur2]) {
                        end();
                        return;
                    }
                }
            }

            cnt++;
            for (int cur : tmp) {
                sb.append(cur).append(' ');
            }
            sb.append('\n');
        }
        System.out.println(cnt);
        System.out.print(sb);
    }

    private void end() {
        System.out.println(0);
    }
}