[SWEA] #1219 길찾기

Link

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14geLqABQCFAYD&categoryId=AV14geLqABQCFAYD&categoryType=CODE

---

Code

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

class Solution {
    static ArrayList<ArrayList<Integer>> arr;
    static int result;
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int testCase = 1; testCase <= 10; testCase++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int tc = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine(), " ");
            arr = new ArrayList<>();
            result = 0;
            for (int i = 0; i < 100; i++) {
                arr.add(new ArrayList<>());
            }
            while (st.hasMoreTokens()) {
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                arr.get(x).add(y);
            }
            for (Integer a : arr.get(0)) {
                bfs(a);
            }
            System.out.printf("#%d %d\n", tc, result);
        }
    }

    public static void bfs(int a) {
        if (a == 99) {
            result = 1;
            return;
        }
        else if (arr.get(a).isEmpty()) {
            return;
        }
        else{
            for (Integer b : arr.get(a)) {
                bfs(b);
            }
        }
    }
}

---

Solution

Scanner말고 BufferedReader와 StringTokenizer를 이용해 입력을 받았다. 백준 문제중 이렇게 안풀면 시간초과가 뜨는 문제가 있음
또한 그래프를 인접행렬말고 인접리스트로 해결하기위해 ArrayList로 그래프를 구현하였고 길찾기는 BFS를 사용하여 99를 찾으면 전역변수 result를 1로 변경하도록 하였다.