글 읽기 - 반례좀 찾아주세요..

hds1630 5년 전 0

Point 좌표 이동하면서 벽을 부쉈는지 안부쉈는지는 check변수로 판단하며 dfs로 구현했는데 반례 좀 찾아주세요...

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	public static void main(String[] args) throws Exception {
		run();
		bw.flush();
		br.close();
		bw.close();
	}

	static int N, M;
	static int map[][];
	static int dist[][];
	static boolean visit[][];
	static boolean check = false;

	static int dx[] = { -1, 0, 1, 0 };
	static int dy[] = { 0, -1, 0, 1 };

	static void run() throws Exception {
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new int[N + 1][M + 1];
		dist = new int[N + 1][M + 1];
		visit = new boolean[N + 1][M + 1];

		for (int i = 1; i <= N; i++) {
			String[] buf = br.readLine().split("");
			for (int j = 1; j <= M; j++) {
				map[i][j] = Integer.parseInt(buf[j - 1]);
			}
		}

		dist[1][1] = 1;
		visit[1][1] = true;
		dfs(new Point(1, 1), check);

		bw.write((dist[N][M] != 0 ? dist[N][M] : -1) + "\n");
	}

	static void dfs(Point p, boolean check) {

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

			if (nx >= 1 && ny >= 1 && nx <= M && ny <= N) {
				if (map[ny][nx] == 0 && !visit[ny][nx]) {
					visit[ny][nx] = true;
					dist[ny][nx] = dist[p.y][p.x] + 1;
					dfs(new Point(nx, ny), check);
				} else if (map[ny][nx] == 1 && check == false && !visit[ny][nx]) {

					visit[ny][nx] = true;
					check = true;
					dist[ny][nx] = dist[p.y][p.x] + 1;
					dfs(new Point(nx, ny), check);
				}
			}

		}
	}

	static class Point {
		int x;
		int y;

		Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

djm03178 5년 전 1

반례를 찾는다고 해결할 정도의 코드가 아닙니다. 근본적으로 풀이가 틀렸습니다.

최단 거리는 DFS로 풀 수 없습니다. 어떤 칸에 처음 도달했을 때의 거리가, 다른 경로를 통해 도달한 거리보다 짧다는 보장이 있나요? 최단 거리는 무조건 BFS입니다.
한 방향에 벽이 있어서 부수고 check를 true로 바꿨습니다. 다른 방향을 봤는데 벽이 없습니다. 그런데도 check는 여전히 true인 상태로 나아가야 할까요?

hds1630 5년 전 0

감사합니다. BFS로 바꿔서 고민해보겠습니다!

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

문제

문제

출처

ICPC

반례좀 찾아주세요..

hds1630 5년 전 0

djm03178 5년 전 1

hds1630 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말