백준 23302 '전파와 병합 2'

Bonwoong Ku·2023년 9월 3일

DFS ps 골드4 구현 그래프 문자열 백준 위상정렬

알고리즘 문제풀이

목록 보기

12/110

아이디어

1. 셀 좌표 파싱과 매핑

문자열 패턴이 복잡하거나 없으면 Map을 쓰는 수밖에 없지만… 기왕 패턴이 주어졌으니 좌표를 정수로 매핑시켜 일반적인 그래프 탐색으로 만들기로 했다.
(알파벳에 해당하는 수) * 1000 + (숫자 좌표) 로 바꾼다.
- “A37” → 1037, “U238” → “21238”, “AC89” → 29089 (= (126+3)1000+89)
- R을 이용해서 더미 인덱스가 없도록 할 수는 있지만 이렇게 하는 편이 디버깅이 쉬우니깐…

2. 입력 처리

StringTokenizer를 이용해 셀 한 개씩 입력을 받는다.
이때 받은 단어?를 “+”를 구분자로 해서 다시 나눈다.
- 나눠진 토큰이 2개라면 두 좌표에 해당하는 간선을 추가하고 각각 진입차수를 올린다.
- 나눠진 토큰이 1개일 때 그 문자열의 길이가 1이면 (즉 “.”이면) 무시한다. 아니라면 간선 추가하고 진입차수 올린다.

3. 정점 개수 세기

모든 셀을 돌며 진입/진출차수 둘 다 0이 아닌 셀만 이 문제에서 관심있는 정점이라 생각하고 개수를 세어 놓는다.
이후 위상 정렬 결과와 비교해야 한다.

4. 위상정렬과 결과 출력

수업 시간에 배운 대로…
위상 정렬을 완료한 후 탐색한 정점 수가 전체 정점보다 작으면 사이클이 있었다는 뜻이다.
사이클 여부에 따라 결과를 출력한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer tk;

    static int IDX_CNT = parseIndex("ZZ999") + 1;

    static int R, C, vCnt;
    static List<List<Integer>> graph = new ArrayList<>();
    static int[] indeg = new int[IDX_CNT];
    static Queue<Integer> q = new ArrayDeque<>();

    public static void main(String[] args) throws Exception{
        for (int i=0; i<IDX_CNT; i++)
            graph.add(new ArrayList<>());

        tk = new StringTokenizer(rd.readLine());
        R = Integer.parseInt(tk.nextToken());
        C = Integer.parseInt(tk.nextToken());

        // 그래프 구성
        for (int y=1; y<=R; y++) {
            tk = new StringTokenizer(rd.readLine());
            for (int x=1; x<=C; x++) {
                int idx = y + x * 1000;
                StringTokenizer ptk = new StringTokenizer(tk.nextToken(), "+");
                if (ptk.countTokens() == 2) {
                    int prcdIdx1 = parseIndex(ptk.nextToken());
                    int prcdIdx2 = parseIndex(ptk.nextToken());
                    graph.get(idx).add(prcdIdx1);
                    graph.get(idx).add(prcdIdx2);
                    indeg[prcdIdx1]++;
                    indeg[prcdIdx2]++;
                }
                else {
                    String s = ptk.nextToken();
                    if (s.length() == 1) continue;  // "."는 노드로 취급 안함
                    int prcdIdx = parseIndex(s);
                    graph.get(idx).add(prcdIdx);
                    indeg[prcdIdx]++;
                }
            }
        }

        // 진입차수가 0이고 진출차수가 1 이상인 정점 큐에 넣기
        // 이때 차수(진입, 진출 상관 없이)가 0이 아닌 정점은 정점 개수에 포함한다.
        for (int i=0; i<IDX_CNT; i++) {
            int outdeg = graph.get(i).size();
            if (indeg[i] > 0 || outdeg > 0)
                vCnt++;
            if (indeg[i] == 0 && outdeg > 0)
                q.offer(i);
        }

        // 위상정렬
        int cnt = 0;
        while (!q.isEmpty()) {
            int n = q.poll();
            for (int m: graph.get(n)) {
                indeg[m]--;
                if (indeg[m] == 0) {
                    q.offer(m);
                }
            }
            cnt++;
        }

        // 정점 총 개수와 위상정렬로 탐색한 정점 수가 일치하지 않으면 사이클 존재
        System.out.println((vCnt > cnt) ? "yes" : "no");

    }

    static int parseIndex(String s) {
        int a = 0, n = 0;
        int i = 0;
        char[] chs = s.toCharArray();
        while (chs[i] >= 'A') a = a * 26 + chs[i++] - 'A' + 1;
        while (i < chs.length) n = n * 10 + chs[i++] - '0';
        return a * 1000 + n;
    }
}