백준 15723 n단 논법

백준 15723 n단 논법

---

• 오늘도 찬웅이형 스터디의 n단 논법을 풀었다. vector를 사용해서 연결되는 리스트만 이어주고, 2차원 배열을 통해 상하좌우를 방문하지 않는다는 점에서 어제 풀었던 문제와
  유사했다. 다양한 DFS 문제를 접하는 것 같아서 참 좋다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.Vector;

public class Boj_15723 {
    static Vector<Vector<Integer>> table = new Vector<Vector<Integer>>();
    public static void main(String[] args) {
        int n;
        Scanner scanner = new Scanner(System.in);
        n = Integer.parseInt(scanner.nextLine());
        for (int i = 0; i <= 26; i++) {
            table.add(new Vector<Integer>());
        }
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(scanner.nextLine());
            int from = st.nextToken().charAt(0);
            st.nextToken();
            int to = st.nextToken().charAt(0);
            table.get(from - 'a').add(to - 'a');
        }
        int m = Integer.parseInt(scanner.nextLine());
        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(scanner.nextLine());
            int from = st.nextToken().charAt(0);
            st.nextToken();
            int to =st.nextToken().charAt(0);

            if (dfs(from - 'a', to - 'a') == true) {
                System.out.println("T");
            } else {
                System.out.println("F");
            }
        }
    }

    public static boolean dfs(int from, int target) {
        int visited[] = new int[26];
        Queue<Integer> q = new LinkedList<>();

        q.add(from);
        visited[from] = 1;
        while(!q.isEmpty()) {
            int cur = q.peek();
            q.remove();
            for (int i = 0; i < table.get(cur).size(); i++) {
                int cur_view = table.get(cur).get(i);
                if (cur_view == target) {
                    return true;
                }
                if (visited[cur_view] == 1) continue;
                visited[cur_view] = 1;
                q.add(cur_view);
            }
        }
        return false;
    }
}

• 문제 자체는 어렵지 않았다. 그냥 dfs 탐색을 하다 타겟이 나오면 바로 리턴해 주었다.
• 오히려 "a" 로 들어온 걸 string -> char -> int 로 바꾸는 과정을 혼동했는데, 그냥 charAt() 로 가져와서 int 에 저장하면
  아스키코드로 저장이 된다.