[백준/BOJ] 2252 줄 세우기 - JAVA

[백준/BOJ] 2252 줄 세우기 - JAVA

문제

https://www.acmicpc.net/problem/2252

 

문제 분석

조건

N명의 학생과, 두 학생의 키를 비교한 M개의 정보가 주어진다.

키 비교 정보는 `A B`형태로 주어지며, A학생이 B학생보다 앞에 서야 한다는 순서 관계를 의미한다. 이 순서 관계를 모두 만족하도록 학생들을 전체 줄 세우는 문제이다.

풀이방법

이 문제는 전형적인 위상 정렬 문제이다. A학생이 B학생보다 앞에 선다는 정보를 바탕으로 `A -> B`형태의 간선을 가지는 그래프로 만들어 문제를 해결했다.

문제에서 진입차수로 작성한 inDegree는 앞에 서야 되는 학생들의 수를 의미한다.

코드

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;public class Main {    public static void main(String[] args) throws IOException {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        int[] originMap = new int[10];        //0일 경우 << 해도 0이기 때문에 처음 1로 초기화 해줘야함        Arrays.fill(originMap, 1);        for (int r = 0; r < 10; r++) {            String line = br.readLine();            for (int c = 0; c < 10; c++) {                originMap[r] = originMap[r] << 1;                if (line.charAt(c) == 'O') {                    originMap[r] |= 1;                }            }        }        // 1줄 2^10        int T = 1 << 10;        int answer = Integer.MAX_VALUE;        for (int tc = 0; tc < T; tc++) {            int[] copyMap = Arrays.copyOf(originMap, 10);            int count = 0;            for (int c = 0; c < 10; c++) {                if (((1 << c) & tc) != 0) {                    turn(copyMap, 0, c);                    count++;                }            }            //2번째줄부터            for (int r = 1; r < 10; r++) {                for (int c = 0; c < 10; c++) {                    if (copyMap[r - 1] == T) {                        //윗줄이 전부 스위치가 꺼진 상태                        break;                    }                    if ((copyMap[r - 1] & (1 << c)) > 0) {                        turn(copyMap, r, c);                        count++;                    }                }            }            if (copyMap[9] == T) {                answer = Math.min(answer, count);            }        }        if (answer == Integer.MAX_VALUE) {            answer = -1;        }        System.out.println(answer);    }    private static void turn(int[] map, int r, int c) {        int[][] dr = {{0, 0}, {1, 0}, {-1, 0}, {0, 1}, {0, -1}};        for (int[] d : dr) {            int nextR = r + d[0];            int nextC = c + d[1];            if (nextR < 0 || nextR >= 10 || nextC < 0 || nextC >= 10) {                continue;            }            //XOR연산            map[nextR] = map[nextR] ^ (1 << nextC);        }    }}import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        List<Integer>[] graph = new List[N + 1];
        int[] inDegree = new int[N + 1];    // 진입 차수
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int front = Integer.parseInt(st.nextToken());
            int back = Integer.parseInt(st.nextToken());
            inDegree[back]++;
            if (graph[front] == null) {
                graph[front] = new ArrayList<>();
            }
            graph[front].add(back);
        }

		// 진입 차수가 0인 노드 큐에 추가
        Queue<Integer> que = new ArrayDeque<>();
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) {
                que.add(i);
            }
        }

        while (!que.isEmpty()) {
            int now = que.poll();
            sb.append(now).append(" ");

            if (graph[now] == null) {
                continue;
            }
            // 현재 노드와 연결된 노드들의 진입 차수 감소
            for (Integer next : graph[now]) {
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    que.add(next);
                }
            }
        }

        System.out.println(sb.toString());
    }
}