[SWEA] 4727번 견우와직녀

견우가 까마귀와 까치의 도움으로 최대한 빠르게 직녀에게 가는 방법을 찾아내자!

BFS에 여러가지 조건을 적용한 문제로, 예전에 풀었던 신호등과 비슷한 문제다.

신호등은 추후에 업로드시 링크를 달아야겠다!

문제를 읽기가 힘들고, 조건을 이해하는게 힘들었다….

[문제] SWEA 4727번 : 견우와 직녀

풀이 방법

BFS를 돌면서 아래의 조건을 만족시킨다.

1. 방문처리는 메모이제이션으로 가장 짧은 시간을 저장하여 확인한다.
2. 오작교는 시간이 T라면 T의 배수에 건널 수 있다.
3. 견우는 절벽을 연속으로 건널 수 없다.
4. 교차하는 곳에는 오작교를 만들 수 없다.
5. 0인 곳 (M인 오작교)는 한 개만 만들 수 있다.

import java.io.*;
import java.util.*;

public class Solution {
	public static int N, M, ans;
	public static int[][] map;
	public static int[][][] v;
	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++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			map = new int[N][N];
			v = new int[N][N][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());
				}
			}
			ans = Integer.MAX_VALUE;
			bfs();
			System.out.println("#"+tc+" "+ans);
		}
	}
	
	public static void bfs() {
		Queue<int[]> que = new LinkedList<int[]>();
		que.offer(new int[] {0, 0, 0, 0});
		v[0][0][0] = -1;
		
		while(!que.isEmpty()) {
			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)) continue;
				if (v[nx][ny][cur[3]] != 0 && v[nx][ny][cur[3]] < cur[2]+1) continue;
				
				if (map[nx][ny] == 1) {
					if (nx == N-1 && ny == N-1) {
						ans = Math.min(ans, cur[2]+1);
						continue;
					}
					que.offer(new int[] {nx, ny, cur[2]+1, cur[3]});
					v[nx][ny][cur[3]] = cur[2]+1;
				}else if (map[cur[0]][cur[1]] == 1){
					int T = 0;
					int flag = 0;
					if (map[nx][ny] > 1) {
						T = map[nx][ny];
						flag = cur[3];
					}
					else if (map[nx][ny] == 0) {
						if (cur[3] == 1) continue;
						if (crossCheck(nx, ny)) continue;
						flag = 1;
						T = M;
					}
					
					int mod = 0;
					if (T == cur[2])      mod = T;
					else if (T < cur[2])  mod = T - (cur[2] % T);
					else                  mod = T - cur[2];
					if (v[nx][ny][1] != 0 && v[nx][ny][1] < cur[2]+mod) continue;
					
					que.offer(new int[] {nx, ny, cur[2]+mod, flag});
					v[nx][ny][1] = cur[2]+mod;
				}
			}
		}
	}
	
	public static boolean isBoundary(int nx, int ny) {
		if (nx < 0 || nx >= N || ny < 0 || ny >= N) return false;
		return true;
	}
	
	public static boolean crossCheck(int x, int y) {
		boolean v = false;
		boolean h = false;
		for (int i = 0; i < 2; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (!isBoundary(nx, ny)) continue;
			if (map[nx][ny] == 0 || map[nx][ny] > 1) v = true; 
		}
		for (int i = 2; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (!isBoundary(nx, ny)) continue;
			if (map[nx][ny] == 0 || map[nx][ny] > 1) h = true; 
		}
		return v&&h;
	}
}

시간제한	메모리 제한	시간	메모리	레벨	풀이 당시 정답율
2초	256MB	157ms	31,232KB	D4	16.63%