[JAVA][SW Expert Academy] 1219. 길찾기

 

 [SW Expert Academy] 1219. 길찾기

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

 

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

SW Expert Academy

---

 문제 내용

그림과 같이 도식화한 지도에서 A도시에서 출발하여 B도시로 가는 길이 존재하는지 조사하려고 한다. 길 중간 중간에는 최대 2개의 갈림길이 존재하고, 모든 길은 일방 통행으로 되돌아오는 것이 불가능하다. 다음과 같이 길이 주어질 때, A도시에서 B도시로 가는 길이 존재하는지 알아내는 프로그램을 작성하여라.  - A와 B는 숫자 0과 99으로 고정된다.  - 모든 길은 순서쌍으로 나타내어진다. 위 예시에서 2번에서 출발 할 수 있는 길의 표현은 (2, 5), (2, 9)로 나타낼 수 있다.  - 가는 길의 개수와 상관없이 한가지 길이라도 존재한다면 길이 존재하는 것이다.  - 단 화살표 방향을 거슬러 돌아갈 수는 없다. [제약 사항] 출발점은 0, 도착점은 99으로 표현된다. 정점(분기점)의 개수는 98개(출발점과 도착점 제외)를 넘어가지 않으며, 한 개의 정점에서 선택할 수 있는 길의 개수도 2개를 넘어가지 않는다. 아래 제시된 가이드 라인은 제안사항일 뿐 강제사항은 아니다. [데이터 저장 가이드] 정점(분기점)의 개수가 최대 100개 이기 때문에, size [100]의 정적 배열 2개을 선언하여, 각 정점의 번호를 주소로 사용하고, 저장되는 데이터는 각 정점에서 도착하는 정점의 번호를 저장한다. 위 그림을 저장하였을 때 결과는 다음과 같다.   [입력] 각 테스트 케이스의 첫 줄에는 테스트 케이스의 번호와 길의 총 개수가 주어지고 그 다음 줄에는 순서쌍이 주어진다. 순서쌍의 경우, 별도로 나누어 표현되는 것이 아니라 숫자의 나열이며, 나열된 순서대로 순서쌍을 이룬다. [출력] #부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스에 대한 답을 출력한다.

 

 

 해결 순서

1. 길이 연결된 순서쌍 A->B, A->C 값을 배열1, 2에 각각 저장 (배열의 길이는 정점의 최대 개수인 100으로 고정)
2. 1개 정점에서 최대 2개의 길로 나누어지며, 연결된 길은 해당 길 번호로 저장

  > ex) 2 -> x & 2 -> y 일 때 arr_r1[2] = x, arr_r2[2] = y
3. 0 -> ... -> 99일 때 길이 존재하면 1, 존재하지 않으면 0으로 출력

 

 

 문제 풀이

import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Solution
{
    static int[] arr_r1;
    static int[] arr_r2;
    static int result;
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = 10;
        
        for(int test_case = 1; test_case <= 10; test_case++)
        {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int TC = Integer.parseInt(st.nextToken());
            int roadCnt = Integer.parseInt(st.nextToken());
            arr_r1 = new int[100];
            arr_r2 = new int[100];
            result = 0;
 
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < roadCnt; i++) {
                int key = Integer.parseInt(st.nextToken());
                int value = Integer.parseInt(st.nextToken());
                if (arr_r1[key] == 0) {
                    arr_r1[key] = value;
                } else {
                    arr_r2[key] = value;
                }
            }
 
            isLinked(arr_r1[0]);
            isLinked(arr_r2[0]);
            
            System.out.println("#" + TC + " " + result);
        }
    }
 
    public static void isLinked(int i) {
        if (i == 99) {
            result = 1;
            return;
        }
        if (i == 0) {
            return;
        }
        if (result == 1) {
            return;
        }
        
        isLinked(arr_r1[i]);
        isLinked(arr_r2[i]);
    }
}