[백준] 3109 빵집 - 그리디 + DFS JAVA

https://www.acmicpc.net/problem/3109

3109번: 빵집

코드설명

그리디 + DFS를 활용하여 해결할 수 있는 문제입니다.

 

이 문제에서 가장 중요한 그리디 개념은, 

만약 첫번째 행에서부터 아래의 행으로 파이프를 설치하기 시작한다면,

각 칸은 오른쪽 위 대각선, 오른쪽, , 오른쪽 아래 대각선 이 순서대로 순서를 보장해야합니다.

만약 맨 아래의 행에서부터 첫번째 행으로 파이프를 설치하기 시작한다면, 

각 칸은 오른쪽 아래 대각선, 오른쪽, 오른쪽 위 대각선 이 순서대로 순서를 보장해야합니다.

 

이러한 개념이 일종의 그리디 개념으로 쓰입니다.

 

두번째, DFS 진행시에 flag == true일때 해당 위치에 도달한 것으로 판정하는데 이떄 아직 DFS를 진행중인 반복문에도 중단처리를해야합니다.

if(flag == true) continue;

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	public static int R, C;
	public static char[][] map;
	public static boolean[][] visited;
	public static int answer = 0;
	public static boolean flag = false;
	public static int[] dx = {-1,0,1}; //우상, 우, 우하
	public static int[] dy = {1,1,1}; //우상, 우 , 우하 
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	R = Integer.parseInt(st.nextToken());
    	C = Integer.parseInt(st.nextToken());
    	
    	map = new char[R][C];
    	for(int i=0;i<R;i++) {
    		st = new StringTokenizer(br.readLine());
    		map[i] = st.nextToken().toCharArray();
    	}
    	
    	visited = new boolean[R][C];
    	for(int i=0;i<R;i++) {
    		flag = false;
    		visited[i][0] = true;
    		simulate(new Node(i, 0));
    		if( flag == true) {
    			answer += 1;
    		}
    		
    	}
    	System.out.println(answer);
    	
    	
    }
    
    public static void simulate(Node node) {

    	if(flag == true) return;
    	
    	if(node.y == C-1) {
    		flag = true;
    		return ;
    	} 
    	
    	for(int dir=0;dir<3;dir++) {
    		int nx = node.x + dx[dir];
    		int ny = node.y + dy[dir];
    		
    		if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
    		if(visited[nx][ny] == true) continue;
    		if(map[nx][ny] == 'x') continue;
    		if(flag == true) continue;
    		
    		visited[nx][ny] = true;
    		simulate(new Node(nx, ny));
    		
    	}
    }
    
}
class Node{
	int x;
	int y;
	public Node(int x, int y) {
		this.x=x;
		this.y=y;
	}
}