[SWEA] 4193번 수영대회 결승전

삼성이를 우승시키기위한 최단 경로의 시간을 출력하자!

신호등 문제로 BFS에 현재시간과 소용돌이를 건널 수 있는 시간을 비교해서 큐에 넣어준다.

소용돌이의 시간이 일정하기 때문에 신호등이나 견우와직녀보다는 비교적 쉬운 문제다.

[문제 출처] SWEA 4193번 : 수영대회 결승전

풀이 방법

1. 시작점을 큐에 넣어준다.
2. 큐 사이즈를 받아서 사이즈 만큼 돌아준다 (시간 체크)
3. 소용돌이를 만날 경우 건널 수 없으면 다시 큐에 넣어준다.

• 2번을 체크해서 BFS를 구현할 경우 visit배열을 int형으로 해줄 필요가 없다 (메모이제이션 불필요)

package may;
import java.io.*;
import java.util.*;

public class Solution {

	public static int N, ans;
	public static int[][] map;
	public static boolean[][] v;
	public static int[] S, E;
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			v = new boolean[N][N];
			S = new int[2];
			E = new int[2];
			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());
				}
			}
			st = new StringTokenizer(br.readLine());
			S[0] = Integer.parseInt(st.nextToken());
			S[1] = Integer.parseInt(st.nextToken());
			st = new StringTokenizer(br.readLine());
			E[0] = Integer.parseInt(st.nextToken());
			E[1] = Integer.parseInt(st.nextToken());
			if (isAnswer(S[0], S[1])) System.out.println("#"+tc+" "+0);
			else System.out.println("#"+tc+" "+bfs());
		}
	}
	
	public static int bfs() {
		Queue<int[]> que = new LinkedList<int[]>();
		que.offer(S);
		v[S[0]][S[1]] = true;
		
		
		int time = 0;
		while(!que.isEmpty()) {
			int size = que.size();
			for (int t = 0; t < size; t++) {
				int[] cur = que.poll();
				for (int i = 0; i < 4; i++) {
					int nx = cur[0] + dx[i];
					int ny = cur[1] + dy[i];
					
					if (!isBoundary(nx, ny) || map[nx][ny] == 1 || v[nx][ny]) continue;
					if (isAnswer(nx, ny)) 
						return time+1;
					if (map[nx][ny] == 2) {
						if ((time < 2 || (time-2)%3 != 0)) {
							que.offer(cur.clone());
							continue;
						}
					}
					que.offer(new int[] {nx, ny});
					v[nx][ny] = true;
				}
			}
			time++;
		}
		return 0;
	}
	
	public static boolean isBoundary(int nx, int ny) {
		return nx >= 0 && nx < N && ny >= 0 && ny < N;
	}
	public static boolean isAnswer(int nx, int ny) {
		return nx == E[0] && ny == E[1];
	}
}

시간제한	메모리 제한	시간	메모리	레벨	풀이 당시 정답율
4초	256MB	111ms	20104KB	D4	35.50%