빵집 [백준 3109][골드1][Java]

 

[광고 누르면 오늘의 행운 상승!!]

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

3109번: 빵집

DFS로 구현하여 목적지에 도달하면 목적지까지의

PATH를 막아서 다시 순회하지 않게 하였다.

import java.io.*;
import java.util.*;

public class Main {
	public static int[] dx = {-1,0,1};
	public static int[] dy = {1,1,1};
	public static boolean[][] visit;
	public static char[][] map;
	public static Queue<int[]> q;
	public static int R, C, pipe;
	public static ArrayList<int[]> list;
	
	public static void main(String[] args) throws Exception {
		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];
		visit = new boolean[R][C];
		for (int i = 0; i < R; i++) {
			char c[] = br.readLine().toCharArray();
			for (int j = 0; j < C; j++) {
				map[i][j] = c[j];
			}
		}
		
		for (int i = 0; i < R; i++) {
			list = new ArrayList<>();
			list.add(new int[] {i,0}); //첫번째 노드 저장
			dfs(i,0); // 세로로 bfs시작
		}
		System.out.println(pipe);

	}

	public static void dfs(int row, int col) {
		visit[row][col] = true;
		
		if(col == C-1) {//빵집에 도착했을 때
			for (int i = 0; i < list.size(); i++) {
				map[list.get(i)[0]][list.get(i)[1]] = 'x'; // 경로를 x로 만듬.
			}
			pipe++;
			return;
		}
		
		for (int i = 0; i < 3; i++) { //3방향으로 탐색
			int nx = row + dx[i];
			int ny = col + dy[i];
			
			if (nx < 0 || nx >= R || ny < 0 || ny >= C) {
				continue;
			}
			if (map[nx][ny] != 'x' && !visit[nx][ny]) { // 땅이고 방문하지 않았을 때
				list.add(new int[] {nx,ny}); //경로 저장
				dfs(nx,ny);
				if(map[row][col] == 'x') return; // 본인이 벽이 되었으면 리턴
			}
		}

	}

}