백준 2252 줄 세우기 [JAVA]

solved.ac = 골드 3

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

2252번: 줄 세우기

 

---

1. 접근

문제 속 요구사항은 일부 학생들의 키 비교 입력을 기준으로 전체 학생들을 줄 세우면 되는 문제입니다.

 

하단 알고리즘 분류를 보시면 알겠지만 그래프를 활용한 문제인데 직접적으로 그래프라고 알려주진 않습니다.

 

또한, 위 문제는 위상 정렬을 활용한 문제로 해당 알고리즘을 모르신다면 간단하게 보고 오시는 걸 추천드립니다!

 

 

앞서 그래프를 활용해야 한다고 말했으니 예제 2번을 통해 그래프를 만들어보면 다음과 같습니다.

 

정점 = 학생번호

간선 = 키 비교 데이터

 

 

그림의 하단을 앞이라고 가정했을 때 예제 입력 2번이 충족된 그래프입니다.

(4번이 2번보다 앞에 있다, 3번이 1번보다 앞에 있다.)

 

물론 위 조건대로 세우면 다른 방법으로도 줄을 세울 수 있지만 문제 속 지문에서 상관없다고 하니 아무거나 출력해주도록 합시다!

 

 

---

2. 풀이

 

변수 세팅

static int N, M;
static ArrayList<Integer>[] graph;
static int[] indeg;
public static void main(String[] args) throws IOException {
    st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    indeg = new int[N + 1];

    graph = new ArrayList[N + 1];
    for (int i = 1; i <= N; i++) graph[i] = new ArrayList<>();
    for (int i = 1; i <= M; i++) {
        st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken());
        graph[x].add(y);
        indeg[y]++; // y로 들어가는 간선 개수 추가
    }
    solution();
}

 

탐색 및 정답 출력

static void solution() {
    Deque<Integer> queue = new LinkedList<>();

    // 들어가는 간선이 없다면 누구든 앞에 갈 수 있다.
    for (int i = 1; i <= N; i++) {
        if (indeg[i] == 0) queue.add(i);
    }

    while(!queue.isEmpty()) {
        int x = queue.poll();
        sb.append(x).append(' ');
        // graph X와 연결된 정점들을 확인한다.
        for (int y : graph[x]) {
            indeg[y]--; // 방문했으니 들어가는 간선이 하나 줄어든다.
            if (indeg[y] == 0) queue.add(y);
        }
    }
    System.out.println(sb.toString());
}

 

---

 

3. 전체 코드