[SWEA] 1219. [S/W 문제해결 기본] Stack1 - 길찾기

문제

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

SW Expert Academy

 

 

풀이

이 문제는 A(0)에서 B(99) 까지 도달할 수 있는지에 대한 여부를 판단하는 문제이다. 스택을 이용하는 단계이지만, 내부적으로 스택을 이용해서 함수를 처리하는 재귀를 이용해서 DFS 방식으로 풀었다. 

문제에 나와있는 가이드 방법대로 할 수 있었지만 기존에 알고리즘 수업 때 배웠던 인접 리스트 방식을 이용해서 구현했다. 인접 리스트는 2차원 벡터를 이용해서 해당 정점에서 도달할 수 있는 정점들을 동적으로 추가할 수 있도록 구현했다.

 

import java.util.*;
 
public class Solution {
    static Scanner scan = new Scanner(System.in);
    static Vector<Vector<Integer>> vec;//각 정점의 인접리스트 만들기위한 2차벡터
    static int[] datas;//그래프 자료 변수
    static int chk = 0;//99 도착 여부 체크 변수
    
    static void dfs(int vertex) {
        if(vertex == 99) {//99에 도착한다면 체크 변수 1로 초기화
            chk = 1;
            return;
        }
        if(chk==0) {//이미 도착하는 경우 찾았다면 더이상 찾을 필요없으니 그 부분 처리
            for(int i=0;i<vec.get(vertex).size();i++)
                dfs(vec.get(vertex).get(i));
        }
    }
    static void make_graph(int num) {
        vec = new Vector<Vector<Integer>>(num);
        for(int j=0;j<num;j++)
            vec.add(new Vector<Integer>());
        
        for(int j=0;j<num*2;j+=2) {
            vec.get(datas[j]).add(datas[j+1]);
        }
    }
    static void solution() {
        for(int i=1;i<=10;i++) {
            scan.nextInt();
            int num = scan.nextInt();
            datas = new int[num*2];
            //데이터 입력
            for(int j=0;j<num*2;j++)
                datas[j] = scan.nextInt();
            
            //그래프 생성
            make_graph(num);
            
            //탐색
            dfs(0);
            System.out.println("#"+i+" "+chk);
            chk = 0;
        }
    }
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        solution();
    }
}