글 읽기 - 해당 문제 dfs로는 안되는지 궁금합니다.

mementohora 3년 전 0

단순히 생각하여 V는 50*50이니

dfs O(V^2)로 생각하여

2500*2500 하면 6백 25만이 나오기에 2초 안에 될 줄 알았는데 아예 안되네요...

어떠한 부분에서 시간이 오래걸리는지 궁금합니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
//	static int[][] tree =new int[3][2]; //이걸로 계속 추적할 필요는 없어보임.
	static char[][] map;
	static int[][][] dp;
	static boolean[][][] visited;
	static int INF = Integer.MAX_VALUE/2;
//	static int treeDir = -1; //0이면 가로 1이면 세로
	static int N;
	public static void main(String[] args) throws Exception{
		//통나무가 바라보고있는 방향 알아야하고
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new char[N][N];
		dp = new int[N][N][2]; //좌 우 방향에 대한 방문 여부
		visited = new boolean[N][N][2];
		int treeIdx = 0;
		int sy=0;
		int sx=0;
		int sd=0;
		for(int i = 0; i < N; i++) {
			String line = br.readLine();
			for(int j = 0 ; j< N; j++) {
				map[i][j] = line.charAt(j);
			}
		}
		loop:for(int i = 0; i < N; i++) {
			for(int j = 0 ; j< N; j++) {
				char next = map[i][j];
				if(next =='B' ) {
					if(map[i][j+1]== 'B') {
						sy = i;
						sx = j+1;
						sd = 0;
					}					
					else {
						sy = i+1;
						sx = j;
						sd = 1;						
					}
					break loop;
				}
			}
		}
		int retVal = dfs(sy,sx,sd);
		if(retVal >= INF) {
			System.out.println(0);
		}
		else
			System.out.println(retVal);
	}
	static int[] delY = {-1,0,1,0};
	static int[] delX = {0,1,0,-1};
	public static int dfs(int y, int x, int d) { //중심의 좌표를 계속 넘길거임
		if(d == 1 && y-1 >= 0 && y+1 < N && map[y-1][x] =='E' && map[y][x] == 'E' && map[y+1][x] == 'E') {
			return 0;
		}
		else if(d == 0 && x-1 >= 0 && x+1 < N && map[y][x-1] =='E' && map[y][x] == 'E' && map[y][x+1] == 'E') {
			return 0;
		}
		else if(dp[y][x][d] != 0 && dp[y][x][d] < INF) {
			return dp[y][x][d];
		}
		int temp = INF;

		for(int i = 0; i < 4; i++) { //상 우 하 좌
			int ny = y +delY[i];
			int nx = x + delX[i];
			//현재 나무 방향과 이동 방향에 대한 바운드 체크랑, 나무 있는지 체크 들어가야함.
			if(check(y,x,i,d) && !visited[y][x][d]) {
				visited[y][x][d] = true;
				temp = Math.min(temp, dfs(ny,nx,d));
				visited[y][x][d] = false;				
			}
		}
		if(check(y,x,5,d)  && !visited[y][x][d]) { //5는 회전
			visited[y][x][d] = true;
			temp = Math.min(temp, dfs(y,x,Math.abs(1-d)));			
			visited[y][x][d] = false;
		}
		return dp[y][x][d] = (temp+1);
	}
	static boolean check(int y, int x, int nextDir, int curTree) {
		boolean retVal = true;
		if(curTree == 0) { //가로
			if(nextDir == 0) { // 북
				if(y-1 < 0)
					retVal = false;
				else {
					for(int i = -1; i <=1; i++) {
						if(map[y-1][x+i] == '1') {
							retVal = false;
							break;
						}
					}
				}
			} 
			else if(nextDir == 1) { //동
				if(x+2 >= N || map[y][x+2]== '1')
					retVal = false;
			}
			else if(nextDir == 2) { //남 
				if(y+1 >= N)
					retVal = false;
				else {
					for(int i = -1; i <=1; i++) {
						if(map[y+1][x+i] == '1') {
							retVal = false;
							break;
						}
					}
				}				
			}
			else if(nextDir == 3){ //서
				if(x-2 <0 || map[y][x-2]== '1')
					retVal = false;
			}
			else {	//회전
				if(y-1 <0 || y+1 >= N)
					retVal = false;
				else {
					for(int i = -1; i <=1; i++) {
						if(map[y+1][x+i] == '1') {
							retVal = false;
							break;
						}
						if(map[y-1][x+i] == '1') {
							retVal = false;
							break;
						}
					}
				}								
			}
		}
		
		else { //현재 트리가 세로
			if(nextDir == 0) {
				if(y-2 <0 || map[y-2][x]== '1')
					retVal = false;
			}
			else if(nextDir == 1) {
				if(x+1 >= N)
					retVal = false;
				else {
					for(int i = -1; i <=1; i++) {
						if(map[y+i][x+1] == '1') {
							retVal = false;
							break;
						}
					}
				}				
			}
			else if(nextDir == 2) {
				if(y+2 >=N || map[y+2][x]== '1')
					retVal = false;
			}
			else if(nextDir == 3) {
				if(x-1 < 0)
					retVal = false;
				else {
					for(int i = -1; i <=1; i++) {
						if(map[y+i][x-1] == '1') {
							retVal = false;
							break;
						}

					}
				}								
			}
			else {
				if(x-1 <0 || x+1 >= N)
					retVal = false;
				else {
					for(int i = -1; i <=1; i++) {
						if(map[y+i][x-1] == '1') {
							retVal = false;
							break;
						}
						if(map[y+i][x+1] == '1') {
							retVal = false;
							break;
						}
					}
				}								
			}			
		}
		return retVal;
	}
}

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

문제

문제

출처

ICPC

해당 문제 dfs로는 안되는지 궁금합니다.

mementohora 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말