글 읽기 - JAVA 탈출 질문합니다....

riimy 4년 전 0

다른 분들께서 올려주신 테스트케이스 대부분은 통과하는데,

20 30
..............................
..............................
.............XXXXXXXXXXX......
.............X...S.....X......
.............X.XXXXXXX.X......
.....XXXXXXXXX.X.....X.X......
........*......X.*...X.X......
.....XXXXXXXXX.X.....X.X......
.............X.X...*.X.X......
.............XDX.....X.X......
.............X.X.....X.X......
.............X.X.....X.X......
.............X.X..*..X.X......
.............X.X.....X.X......
.............X.X.....X.X......
.............X.XXXXXXX.X......
.............X.........X......
.............XXXXXXXXXXX......
..............................
..............................
33

해당 테스트 케이스에서 문제가 생깁니다.

문제를 잘못이해한건가요...?

아무리 생각해도 저에겐 9가 정답이라서요...

제 코드는 물(ww배열)의 이동경로와 두더지(aa배열)의 이동경로를 구하고

따로 canGo라는 메소드와 go라느 배열을 통하여, 두더지와 물 배열의 수를 비교하여 두더지가 더 작으면 go라는 배열에 두더지(aa배열)의 수를 복사했습니다...

package net.acmicpc;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class boj_3055_탈출 {
	static int R, C, startX, startY, endX, endY;
	static int[][] ww, aa, go;
	static boolean[][] waterVisited, visited;
	static boolean[][] animalvisited;
	static char[][] map;
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
	static Queue<int[]> que;

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		R = scanner.nextInt();
		C = scanner.nextInt();

		map = new char[R][C];
		animalvisited = new boolean[R][C];
		waterVisited = new boolean[R][C];
		visited = new boolean[R][C];
		ww = new int[R][C];
		aa = new int[R][C];
		go = new int[R][C];
		for (int i = 0; i < R; i++) {
			String s = scanner.next();
			for (int j = 0; j < C; j++) {
				map[i][j] = s.charAt(j);

				if (map[i][j] == 'S') {
					startY = i;
					startX = j;
				}
				if (map[i][j] == 'D') {
					endY = i;
					endX = j;
					ww[i][j] = -1;
				}
				if (map[i][j] == 'X') {
					ww[i][j] = -1;
					aa[i][j] = -1;
				}

				if (map[i][j] == '*') {
					aa[i][j] = -1;
				}

			}
		}
//		print(map);
		// INPUT
		que = new LinkedList<>();
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (map[i][j] == '*') {
					que.offer(new int[] { i, j });
					ww[i][j] = 0;
					waterVisited[i][j] = true;
				}
			}
		}

		while (!que.isEmpty()) {
			int[] cu = que.poll();
			int y = cu[0];
			int x = cu[1];
			for (int d = 0; d < 4; d++) {
				int ny = y + dy[d];
				int nx = x + dx[d];
				if (safe(ny, nx) && !waterVisited[ny][nx] && ww[ny][nx] == 0 && map[ny][nx] != 'X'
						&& map[ny][nx] != 'D') {
					ww[ny][nx] = ww[y][x] + 1;
					waterVisited[ny][nx] = true;
					que.offer(new int[] { ny, nx });
				}

			}
		}

		animal(startY, startX);
		canGo(startY, startX);
		
		if(go[endY][endX] != aa[endY][endX] || go[endY][endX]==0) {
			System.out.println("KAKTUS");
		}
		else {
			System.out.println(aa[endY][endX]);
		}
	}

	private static void animal(int i, int j) {
		Queue<int[]> que = new LinkedList<>();
		que.offer(new int[] { i, j });
		animalvisited[i][j] = true;
		aa[i][j] = 0;
		while (!que.isEmpty()) {
			int[] cu = que.poll();
			int y = cu[0];
			int x = cu[1];

			for (int d = 0; d < 4; d++) {
				int ny = y + dy[d];
				int nx = x + dx[d];
				if (safe(ny, nx) && !animalvisited[ny][nx] && map[ny][nx] != '*' && map[ny][nx] != 'X') {
					aa[ny][nx] = aa[y][x] + 1;
					animalvisited[ny][nx] = true;
					que.offer(new int[] { ny, nx });
				}
			}
		}
	}

	public static void canGo(int i, int j) {
		Queue<int[]> que = new LinkedList<>();
		que.offer(new int[] { i, j });
		visited[i][j] = true;
		go[i][j] = 0;

		while (!que.isEmpty()) {
			int[] cu = que.poll();
			int y = cu[0];
			int x = cu[1];

			for (int d = 0; d < 4; d++) {
				int ny = y + dy[d];
				int nx = x + dx[d];

				if (safe(ny, nx) && ww[ny][nx] == 0 && !visited[ny][nx]) {
					go[ny][nx] = aa[ny][nx];
					visited[ny][nx] = true;
					que.offer(new int[] { ny, nx });
				}
				if (safe(ny, nx) && aa[ny][nx] != -1 && !visited[ny][nx]) {
					if ((ny == endY && nx == endX) || (aa[ny][nx] < ww[ny][nx])) {
						go[ny][nx] = aa[ny][nx];
						visited[ny][nx] = true;
						que.offer(new int[] { ny, nx });
					}
				}
			}
		}
	}

	/////////////////////////////////////////////////////////////////////////////////////////////
	public static boolean safe(int y, int x) {
		if (y < R && x < C && y >= 0 && x >= 0) {
			return true;
		} else {
			return false;
		}
	}

	public static void print(int[][] lst) {
		for (int i = 0; i < lst.length; i++) {
			for (int j = 0; j < lst[i].length; j++) {
				System.out.print(lst[i][j] + "\t");
			}
			System.out.println();
		}
		System.out.println();
	}

	public static void print(char[][] lst) {
		for (int i = 0; i < lst.length; i++) {
			for (int j = 0; j < lst[i].length; j++) {
				System.out.print(lst[i][j] + "\t");
			}
			System.out.println();
		}
		System.out.println();
	}
}

djm03178 4년 전 1

왜 9가 정답이라고 생각하시나요?

왼쪽으로 출발해서 아래로 내려가는 길로 된다고 생각하신 거라면, 가는 길에 물과 동시에 교차로에서 만나기 때문에 갈 수 없습니다.

riimy 4년 전 0

감사합니다. 두더지 위치를 추적하는 접근 방식을 조금 바꿔보았더니 맞을 수 있었습니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

JAVA 탈출 질문합니다....

riimy 4년 전 0

djm03178 4년 전 1

riimy 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말