[백준 - 19952] 골드4 - 인성 문제 있어??

www.acmicpc.net/problem/19952

19952번: 인성 문제 있어??

1. 유형

시뮬레이션

 

2. 풀이

 

이 문제의 핵심은 3차원 배열을 사용해서 bfs를 사용할 수 있는가 이다.

 

3. 코드

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 Main {

	static int T, H, W, O, F, startr, startc, desr, desc;
	static int map[][];
	static int dr[] = { -1, 0, 1, 0 };
	static int dc[] = { 0, 1, 0, -1 };
	static boolean visit[][][];

	static class Pair {
		int r, c, f;

		public Pair(int r, int c, int f) {
			// TODO Auto-generated constructor stub
			this.r = r;
			this.c = c;
			this.f = f;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		T = Integer.valueOf(st.nextToken());
		for (int tc = 0; tc < T; tc++) {
			st = new StringTokenizer(in.readLine(), " ");
			H = Integer.valueOf(st.nextToken());
			W = Integer.valueOf(st.nextToken());
			O = Integer.valueOf(st.nextToken());
			F = Integer.valueOf(st.nextToken());
			startr = Integer.valueOf(st.nextToken()) - 1;
			startc = Integer.valueOf(st.nextToken()) - 1;
			desr = Integer.valueOf(st.nextToken()) - 1;
			desc = Integer.valueOf(st.nextToken()) - 1;
			map = new int[H][W];
			for (int i = 0; i < O; i++) {
				st = new StringTokenizer(in.readLine(), " ");
				int y, x, w;
				y = Integer.valueOf(st.nextToken()) - 1;
				x = Integer.valueOf(st.nextToken()) - 1;
				w = Integer.valueOf(st.nextToken());
				map[y][x] = w;
			}
			if (bfs()) {
				System.out.println("잘했어!!");
			} else {
				System.out.println("인성 문제있어??");
			}
		}
	}

	static boolean bfs() {
		boolean flag = false;
		Queue<Pair> q = new LinkedList<>();
		visit = new boolean[F + 1][H][W];
		visit[F][startr][startc] = true;
		q.add(new Pair(startr, startc, F));
		while (!q.isEmpty()) {
			Pair cur = q.poll();
			if (cur.r == desr && cur.c == desc) {
				flag = true;
				break;
			}
			if (cur.f < 1) {
				continue;
			}
			for (int i = 0; i < 4; i++) {
				int nr = cur.r + dr[i];
				int nc = cur.c + dc[i];
				int nf = cur.f - 1;
				if (nr < 0 || nc < 0 || nr >= H || nc >= W)
					continue;
				// 더 큰 경우
				if (map[nr][nc] > map[cur.r][cur.c]) {
					if (visit[nf][nr][nc])
						continue;
					if (cur.f >= (map[nr][nc] - map[cur.r][cur.c])) {
						visit[nf][nr][nc]=true;
						q.add(new Pair(nr, nc, nf));
					}
				} else {
					if (visit[nf][nr][nc])
						continue;
					visit[nf][nr][nc]=true;
					q.add(new Pair(nr, nc, nf));
					
				}
			}
		}
		return flag;
	}
}

 

4. 느낀점

 

문제의 조건을 잘 읽어야 겠다. 다 구현하고 문제의 조건이 틀려서 조금 해맨거 같다.

 

비슷한 문제는 백준 1600번이다.

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이