견우와 직녀 [SWEA 4727][JAVA][D4][BFS]

 

[광고 누르면 오늘의 행운 상승!!]

https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AWSHOpR6f_sDFARw&categoryId=AWSHOpR6f_sDFARw&categoryType=CODE

SW Expert Academy

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

1. 참고사항

- 자신의 이동거리(cnt)로 나누어떨어지면 건널 수 있는 다리이다.
- 주기M자리 다리(새로 놓은 다리)는 한번밖에 건너지 못한다.
- 교차로 처리를 해주어야 한다.
- 3차원 visit배열을 이용하여 다리를 놓았을 경우와 놓지 않았을 경우를 따로 처리해주었다.
- 모든 다리에 주기가 M인 다리를 놓았다는 가정하에 실행했다.

2. 구현

- bfs로 뻗어나가면서 앞에 다리가 있으면 다리를 건널 수 있는지 판단한다(자신의 이동거리로 나누어지는지)
- 건너갈 수 있다면 새로 놓은다리인지 원래 놓인 다리인지 판단한다. 
- 새로놓은 다리라면 isAble을 1로 만들고 3차원 visit배열을 true시키고 다시 나아간다.
- 새로 놓은 다리를 두번 밟는다면 continue;
- 다리를 건널 수 없을 때 그 자리에서 기다린다.

import java.io.*;
import java.util.*;
 
public class Solution {
    static class Dog {
        int row, col, cnt;
        int isAble;
 
        public Dog(int row, int col, int cnt, int isAble) {
            this.row = row;
            this.col = col;
            this.cnt = cnt;
            this.isAble = isAble;
        }
    }
    static int dx[] = { 1, 0, -1, 0 };
    static int dy[] = { 0, -1, 0, 1 };
    static int[][] map;
    static boolean[][][] visit;
    static int N, M, ans;
    public static void main(String[] args) throws Exception {
        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());
            M = Integer.parseInt(st.nextToken());
 
            map = new int[N][N];
            visit = new boolean[2][N][N];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
 
            bfs(0, 0);
            System.out.println("#" + tc + " " + ans);
        }
    }
 
    public static boolean isCross(int row, int col) {
        for (int i = 0; i < 4; i++) {
            int j = (i + 1) % 4;
            int r1 = row + dx[i];
            int c1 = col + dy[i];
            int r2 = row + dx[j];
            int c2 = col + dy[j];
            if (inside(r1, c1) && inside(r2, c2) && map[r1][c1] == 0 && map[r2][c2] == 0) {
                return true;
            }
        }
        return false;
    }
     
     public static boolean inside(int row, int col) {
            return row >= 0 && col >= 0 && row < N && col < N;
        }
     
    private static void bfs(int row, int col) {
        Queue<Dog> q = new LinkedList<>();
        visit[0][row][col] = true;
        q.add(new Dog(row, col, 0, 0));
 
        while (!q.isEmpty()) {
            int size = q.size();
            Dog dog;
            for (int i = 0; i < size; i++) {
                dog = q.poll();
                for (int dir = 0; dir < 4; dir++) {
                    int nx = dog.row + dx[dir];
                    int ny = dog.col + dy[dir];
 
                    if (nx < 0 || nx >= N || ny < 0 || ny >= N)
                        continue;
 
                    // 도착지
                    if (nx == N - 1 && ny == N - 1) {
                        ans = dog.cnt + 1;
                        return;
                    }
                    // 방문했으면
                    if (visit[dog.isAble][nx][ny])
                        continue;
 
                    // 다리를 건널 수 있을 때
                    if (map[nx][ny] != 1) {
                        // 다리에서 다리 x(교차로 포함)
                        if (map[dog.row][dog.col] != 1 || isCross(nx, ny)) continue;
                         
                        int time = map[nx][ny];
                        int isAble = dog.isAble;
                        // 새로 만든 다리(주기M짜리)를 밟아봤으면 continue;
                        if (map[nx][ny] == 0) {
                            if (dog.isAble == 1) continue;
                            time = M;
                            isAble = 1;
                        } 
                         
                        // 다리를 건널 수 없을 때
                        if ((dog.cnt + 1) % time != 0) {
                            q.add(new Dog(dog.row, dog.col, dog.cnt + 1, dog.isAble));
                            continue;
                        }
                        visit[isAble][nx][ny] = true;
                        q.add(new Dog(nx, ny, dog.cnt + 1, isAble));
                    }
                    // 그냥 길
                    if (map[nx][ny] == 1) {
                        visit[dog.isAble][nx][ny] = true;
                        q.add(new Dog(nx, ny, dog.cnt + 1, dog.isAble));
                    }
                }
            }
        }
    }
}