[SWEA]4193번:수영대회결승전(JAVA)

https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AWKaG6_6AGQDFARV& 

SW Expert Academy

---

• 알고리즘[풀이방법]

BFS문제. 나의 위치와 흐른 시간을 넣을 class Pos를 만들고, Queue에 넣어 돌린다. 소용돌이는 이동하지 않지만, 3초가 흐를 때마다 멈춘다. 소용돌이가 멈춘 시점에 그 칸을 지나가게 하기 위해서 time을 계속 계산해야한다! 소용돌이가 잦아든 순간까지 그 위치에서 기다려야 하기때문에 이동하지 않은 상태로 시간만 1초 흐르게 다시 Queue에 집어 넣는다. 소용돌이가 멈춘 순간(time%3==2)일 경우 한 칸 나아가고 큐에 들어간당.

처음엔 소용돌이가 멈출 때까지 기다리고 난 다음 시간을 더하고 계산하려고 했다. 이렇게 풀면 더 오랜 시간이 걸려도 먼저 return 되기 때문에 틀림!!! 주어진 테케는 맞았는데 9/15개만 맞아서 다시 풀었땅..

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class S006_SWEA4193_수영대회결승전 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine());
		// 섬은 1, 소용돌이는 2 -> 2초유지,1초 잠잠
		for (int tc = 1; tc <= T; tc++) {
			int answer = -1;
			int N = Integer.parseInt(br.readLine());
			int[][] arr = new int[N][N];
			boolean visited[][] = new boolean[N][N];
			Queue<Pos> mq = new ArrayDeque<>();
			int[][] move = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			st = new StringTokenizer(br.readLine());
			int sr = Integer.parseInt(st.nextToken());
			int sc = Integer.parseInt(st.nextToken());
			mq.add(new Pos(sr, sc, 0));

			st = new StringTokenizer(br.readLine());
			int er = Integer.parseInt(st.nextToken());
			int ec = Integer.parseInt(st.nextToken());

        while (!mq.isEmpty()) {
            Pos tmp = mq.poll();
            if (tmp.r == er && tmp.c == ec) {
                answer = tmp.time;
                break;
            }

            for (int i = 0; i < 4; i++) {
                int nr = tmp.r + move[i][0];
                int nc = tmp.c + move[i][1];
                if (nr >= 0 && nr < N && nc >= 0 && nc < N) {
                    if (!visited[nr][nc]) {
                        if (arr[nr][nc] == 0) {
                            mq.add(new Pos(nr, nc, tmp.time + 1));
                            visited[nr][nc] = true;
                        } else if (arr[nr][nc] == 2) {
                            if (tmp.time % 3 == 2) {
                                mq.add(new Pos(nr, nc, tmp.time + 1));
                                visited[nr][nc] = true;
                            } else {
                                mq.add(new Pos(tmp.r,tmp.c,tmp.time+1));
                            }
                        }
                    }
                }
            }
        } // bfs

			System.out.println("#" + tc + " " + answer);
		} // tc

	}// main

	static class Pos {
		int r, c, time;
\
		public Pos(int r, int c, int time) {
			super();
			this.r = r;
			this.c = c;
			this.time = time;
		}

	}
}// class