[SWEA] S/W 문제해결 기본(4) - 길찾기

[1219] 길찾기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14geLqABQCFAYD

• 문제 설명에 오류가 많아서 댓글에 사람들이 화나있음
• 출발점 0에서 도착점 99까지 가는 길이 존재하는지 조사하는 문제
• 길이 존재하면 1, 없으면 0을 출력한다.

 

 

Solution

• 한 정점에서 최대 갈림길이 2개 이므로 다음과 같이 map[100][2]을 만듦
• bfs로 인접 정점을 따라 가는길에 99를 발견하면 종료
• 입력되는 경로에서 99번이 없는 경우도 있으므로 체크해야한다.

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution {
    static int T, n, m, answer;
    static String str;
    static StringTokenizer st;
    static int[][] map, visited;
    static Queue<Integer> q;
 
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        while (true) {
            st = new StringTokenizer(br.readLine());
            T = stoi(st.nextToken());
            n = stoi(st.nextToken());
            init();
 
            boolean flag = false;
            int from, to;
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                from = stoi(st.nextToken());
                to = stoi(st.nextToken());
 
                if (to == 99)
                    flag = true;
                if (map[from][0] == 0) {
                    map[from][0] = to;
                } else {
                    map[from][1] = to;
                }
            }
 
            if (flag) {
                System.out.println("#" + T + " " + solve(0));
            } else {
                System.out.println("#" + T + " " + 0);
            }
            
            if(T == 10) break;
        }
 
    }
 
    static int solve(int start) {
        q.offer(start);
        visited[0][0] = 1;
        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int i = 0; i<map[cur].length; i++) {
                int next = map[cur][i];
                if (next == 99)
                    return 1;
 
                if (visited[next][i] == 1)
                    continue;
                q.offer(next);
                visited[next][i] = 1; 
            }
 
        }
        return 0;
    }
 
    static void init() {
        map = new int[100][2];
        visited = new int[100][2];
        q = new LinkedList<>();
    }
 
    static int stoi(String s) {
        return Integer.parseInt(s);
    }
}