[SW expert Academy] SWEA 1219번 길찾기 자바(Java)

[D4] [S/W 문제해결 기본] 4일차 - 길찾기 - 1219

문제 링크

성능 요약

메모리: 17,964 KB, 시간: 107 ms, 코드길이: 1,725 Bytes

제출 일자

2024-01-02 00:50

접근 방법

1. 일단 테스트 케이스는 10개임 ( 명시가 안돼서 불편했다.)

2. 그래프는 총 100개의 노드가 있고 0부터 99까지 있음

3. 0부터 99까지 가야한다. 최대 간선은 두개뿐이기에 배열은 [100][2]로 생성

4. 만약 [start][0]이 존재한다면 [1]에 저장한다.

5. 스택에 넣어준 뒤 빼주면서 visit에 방문처리를 해준다.

6. 만약 방문이 된 곳이라면 넘어가고 방문 하지 않았다면 스택에 넣어줌

 

풀이 코드

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

class Solution {
    static int[][] graph;
    static boolean[] visit;
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        for(int tc = 1; tc <= 10; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            st.nextToken();
            int n = Integer.parseInt(st.nextToken());

            // 최대 노드는 100개 최대 간선은 2개
            graph = new int[100][2];
            visit = new boolean[100];
            st = new StringTokenizer(br.readLine());
            for(int i = 0 ; i < n; i++){
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                // 처음 연결하는 간선이라면 연결
                if(graph[start][0] == 0){
                    graph[start][0] = end;
                }else{
                    // 처음 연결이 아니라면 두번째 간선에 연결
                    graph[start][1] = end;
                }
            }

            sb.append("#" + tc + " " + (checkPath() ? "1" : "0")).append("\n");
        }
        System.out.println(sb);
    }
    private static boolean checkPath(){
        Stack<Integer> stack = new Stack<>();
        // 시작 지점 스택에 삽입
        stack.push(0);

        while(!stack.isEmpty()){
            // 현재 스택에 탑을 빼서 저장
            int cur = stack.pop();
            // 현재 노드를 방문처리
            visit[cur] = true;
            // 목표 노드라면 return true로 숏컷
            if(cur == 99) return true;

            // 첫번째 길이 연결 됐고 방문하지 않았다면 스택에 넣어줌
            int next = graph[cur][0];
            if(next != 0 && !visit[next]){
                stack.push(next);
            }

            // 두번째 길이 연결됐고 방문하지 않았다면 스택에 넣어줌
            next = graph[cur][1];
            if(next != 0 && !visit[next]){
                stack.push(next);
            }
        }
        return false;
    }
}

출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do

SW Expert Academy