백준 1103번(JAVA)

이 문제는 DFS와 다이나믹프로그래밍을 모두 적용시켜야 하는 문제이다.

DFS를 진행하는도중 만약 방문된곳을 한번 더 방문했다면 바로 -1을 출력하고 프로그램을 종료시켰다

왜?? 경로에 사이클이 생성되었다는 뜻이기 때문이다.

DP배열은 단순히 해당 지점까지의 게임횟수를 의미한다. 

그런데 만약 다음지점에서의 dp값이 10이다. 근데 현재 지점에서까지의 게임횟수는 5이면 다음지점으로 넘어갈 필요가 있는가? 답은 X다. 왜냐하면 우리는 최대게임횟수를 찾는것이기 때문이다. 

위의 내용을 머리에 넣고 아래 소스코드를 보면 이해가 갈것이다.

 

 

소스코드

import java.io.*;
import java.util.*;
public class Main {

	public static int N;
	public static int M;
	public static int[][] map;
	public static int[][] dp;
	public static int max;
	public static boolean[][] visited;
	public static int[] dx= {-1,0,1,0};
	public static int[] dy= {0,1,0,-1};
	public static void DFS(int y,int x,int count)
	{
		dp[y][x]=count;
		max=Math.max(max, dp[y][x]);//최대값과 현재지점에서의 게임횟수중 큰값을 최대값으로 갱신
		visited[y][x]=true;
		for(int i=0;i<4;i++)
		{
			int ny=y+map[y][x]*dy[i];
			int nx=x+map[y][x]*dx[i];
			if(ny>=0&&ny<N&&nx>=0&&nx<M)
			{		
				if(visited[ny][nx])//경로가 진행중 사이클이 생성됨을 감지하면 -1출력하고 프로그램종료
				{
					System.out.println("-1");
					System.exit(0);
				}
				if(count<dp[ny][nx])//현재까지의 게임 횟수가 다음지점에서의 게임횟수보다 작으면 걍 안간다. 최대값을 찾는문제니깐
				{
					
				}
				else if(map[ny][nx]==0)//마찬가지로 다음이 구멍이라면 게임을 진행할수가없다.
				{
					
				}
				else
				{
					DFS(ny,nx,count+1);//위에 조건을 모두 통과했으면 다음지점에서 DFS실시
				}
			}
		}
		visited[y][x]=false;
	}
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String[] s=br.readLine().split(" ");
		N=Integer.parseInt(s[0]);
		M=Integer.parseInt(s[1]);
		map=new int[N][M];
		dp=new int[N][M];//결과값 
		visited=new boolean[N][M];//방문했는지 확인
		for(int i=0;i<N;i++)//입력 받기
		{
			s=br.readLine().split("");
			for(int j=0;j<M;j++)
			{
				if(s[j].equals("H"))//구멍이면 그냥 0으로 표시
				{
					map[i][j]=0;
				}
				else
				{
					map[i][j]=Integer.parseInt(s[j]);
				}
			}
		}
		DFS(0,0,0);
		System.out.println(max+1);
	}
}

 

 

댓글과 지적은 언제든지 환영입니다~!

글이 마음에 들었다면 왼쪽 이미지를 눌러 후원 부탁드립니다><