글 읽기 - DFS로 풀었는데 반례를 못찾겠어요....

dhseo89 5년 전 0

안녕하세요

겨우겨우 풀어서 제시된 예제는 다 맞혔는데

반례를 못찾겠네요.. 시간초과도 날거같은 느낌인데...

제꺼 한번만 봐주실래요? ㅜㅜ

import java.util.Scanner;

public class Main {

	static int N;
	static int M;
	static char[][] map;
	static String[] rows;
	static int dx[] = {0,0,-1,1};
	static int dy[] = {-1,1,0,0};
	static int min = Integer.MAX_VALUE;
	static boolean visited[][];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		rows = new String[N];
		map = new char[N][M];
		visited = new boolean[N][M];
		Loca Rloc = null;
		Loca Bloc = null;
		for (int i = 0; i < N; i++) {
			rows[i] = sc.next();
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = rows[i].charAt(j);
				if(map[i][j] == 'B') {
					Bloc = new Loca(i,j);
				}
				else if(map[i][j] == 'R') {
					Rloc = new Loca(i,j);
					visited[i][j] = true;
				}
			}
		}
		dfs(Rloc,Bloc,new Loca(0,0),0);
		System.out.println(min == Integer.MAX_VALUE ? -1 : min); //아예 못나가는 경우
	}

	private static void dfs(Loca locR, Loca locB, Loca index, int cnt) {
		if(map[locR.x][locR.y] == 'O') {
			//해당 라인에 파란색 구슬이 있는지 확인
			if(blueChk(locB, index)) min = -1;
			else if(min > cnt ) min = cnt; 
			return;
		}
		int ix = index.x;
		int iy = index.y;
		if(cnt  > 10) return; //10 이상이면 탈출
		for (int i = 0; i < dx.length; i++) {
			int rx = locR.x + dx[i];
			int ry = locR.y + dy[i];
			int bx = locB.x + dx[i];
			int by = locB.y + dy[i];
			if(rx == bx && by == ry) continue; //움직이고 같은 칸에 존재하면 스킵
			if(rx == locB.x && locB.y == ry) continue; //빨간색만 움직이고 같은 칸에 존재하면 스킵
			if(rx <0 || rx> N-1 || ry <0 || ry> M-1 || bx <0 || bx> N-1 || by <0 || by> M-1) continue; //범위를 벗어난다면 스킵
			if(map[rx][ry] == '#') continue; //벽을 만난다면 스킵
			if(map[bx][by] == '#') { //파란구슬이 벽이면 이동안함
				bx = locB.x;
				by = locB.y;
			}
			if(visited[rx][ry]) continue; //방문했던곳이면 
			
			if(ix != dx[i] || iy != dy[i]) {
				cnt = cnt+1;
			}
			
			visited[rx][ry] = true;
			dfs(new Loca(rx,ry), new Loca(bx,by),new Loca(dx[i],dy[i]),cnt);
			visited[rx][ry] = false;
		}
	}

	private static boolean blueChk(Loca locB, Loca index) {
		
		int x = locB.x;
		int y = locB.y;
		while(map[x][y] != '#') {
			x += index.x;
			y += index.y;
			
			if(map[x][y] == 'O') {
				return true;
			}
		}
		return false;
	}
}

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

bhs9158 5년 전 1

블로그에 TC 100개를 만들어서 올려봤습니다.

https://boohyunsik.github.io/e...

참고해보시면 좋을 것 같습니다^^

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

문제

문제

출처

ICPC

DFS로 풀었는데 반례를 못찾겠어요....

dhseo89 5년 전 0

bhs9158 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말