1219. 길찾기

SW Expert 1219. 길찾기

 

* 문제의 저작권은 SW Expert에 있습니다.

 

 

 

 

 

 

[문제 접근]

 

BFS로 접근 해서 size 100 배열 2개 선언 해주고 각 숫자들 넣어주고 map[0][0]일때만 큐에 값을 넣어준 다음

x를 map[1][0]의 값을 넣어 큐에 저장하고 x의 값이 99가 되면 result가 1이 되는 것으로 계획함

 

이런 방식으로 풀다가 배열 두개를 동시에 쓰려니 너무 어렵고 코드가 중복 될 것 같아서 2차원 배열 하나 쓰는걸로 바꿨다

a->b로 가는 길이 있는 경우 1로 , 없는 경우는 0으로 표시했다.

그리고 나머지는 원래 처음 생각하던 방향대로 했다.

 

처음 제출할 때는 다음 map의 방문 여부를 체크하지 않아도 PASS가 됐다.

그리고 처음 시작점 일 때 모든 경우를 다 넣고 시작하든, 하나씩 넣든 상관이 PASS가 됐다.

-> 동시다발적이게 실행되는게 아니기 때문에 상관없는 것 같다.

 

 

 

 

 

 

[코드]

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_1219 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        for (int test_case = 1; test_case <= 10; test_case++) {
            st = new StringTokenizer(br.readLine());
            int tc = Integer.parseInt(st.nextToken()); //테스트 케이스
            int way = Integer.parseInt(st.nextToken()); //길의 개수

            int[][] map = new int[100][100]; //길의 크기

            st = new StringTokenizer(br.readLine());

            for (int i = 0; i < way; i++) {
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[x][y] = 1; //간선을 1로 표시
            }

            boolean[][] visit = new boolean[100][100]; //방문 여부 체크 배열
            Queue<Cord> queue = new LinkedList<>();
            int result = 0;

            for (int j = 0; j < 100; j++) {
                if (map[0][j] == 1) { //시작점이 0이기 때문에 시작점과 연결된 곳을 찾아서
                    queue.offer(new Cord(0, j)); //큐에 모두 담아준다
                }
            }

            while (!queue.isEmpty()) {
                Cord temp = queue.poll();

                if (visit[temp.x][temp.y]) { //방문했으면 넘어감
                    continue;
                }

                visit[temp.x][temp.y] = true; //방문하지 않았을 경우

                int nx = temp.y; //temp.y의 값이 연결된 곳이기 때문에 다음 x로 잡아준다
                for (int i = 0; i < 100; i++) {
                    if (map[nx][i] == 1 && !visit[nx][i]) { //다음 x,i와 연결되어있고 방문하지 않았다면
                        queue.offer(new Cord(nx, i)); //넣어준다.
                    }

                    if (nx == 99) { //다음 x의 값이 99면 도착지점
                        result = 1;
                    }
                }
            }
            System.out.println("#"+test_case + " "  + result);
        }
    }
    static class Cord{
        int x;
        int y;

        public Cord(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }
    }
}