[JAVA][SWEA][BFS] 4193. 수영대회 결승전

4193. 수영대회 결승전

SW Expert Academy

 

 

• 조건문 잘 확인하기
• visited를 boolean으로 하고 Node 값으로 시간 전달

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 sw4193 {
    static int[][] graph;
    static boolean[][] visited;
    static int n;
    static int result;
    static Queue<Node> queue;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static class Node {
        int x, y, time;

        public Node(int x, int y, int time) {
            this.x = x;
            this.y = y;
            this.time = time;
        }
    }

    private static void bfs(int startX, int startY, int endX, int endY) {
        queue.offer(new Node(startX,startY,0));
        visited[startX][startY]=true;

        while(!queue.isEmpty()){
            Node node=queue.poll();
            int x= node.x;
            int y= node.y;
            int time= node.time;

            for (int i = 0; i < 4; i++) {
                int nx=x+dx[i];
                int ny=y+dy[i];

                if (nx==endX && ny==endY){
                    result=time+1; //다음 위치가 도착점이므로 +1
                    return;
                }

                if (nx<0 || nx>=n|| ny<0 || ny>=n || visited[nx][ny]) continue;
                if (graph[nx][ny]==1) continue;
                else if (graph[nx][ny]==2 && time %3 !=2){
                        queue.offer(new Node(x,y,time+1));
                }
                else{
                    visited[nx][ny]=true;
                    queue.offer(new Node(nx,ny,time+1));
                }
            }
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());

        for (int tc = 1; tc <= T; tc++) {
            st=new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());

            graph = new int[n][n];
            visited = new boolean[n][n];
            queue = new LinkedList<>();

            for (int i = 0; i < n; i++) {
                st=new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    graph[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            st=new StringTokenizer(br.readLine());
            int startX = Integer.parseInt(st.nextToken());
            int startY = Integer.parseInt(st.nextToken());
            st=new StringTokenizer(br.readLine());
            int endX = Integer.parseInt(st.nextToken());
            int endY = Integer.parseInt(st.nextToken());

            result = -1;

            if (startX == endX && startY == endY) {
                System.out.printf("#%d %d\n", tc, 0);
            }
            else{
                bfs(startX, startY, endX, endY);

                System.out.printf("#%d %d\n", tc, result);
            }

        }
    }
}