[백준 3109] 빵집

[문제 바로가기]👇

3109번: 빵집

 

💡풀이💡

문제에서 알 수 있는 정보

1. 파이프 시작은 첫 번째 열부터!(0번째 열부터) → 마지막 열에서 종료(C-1번째 열에서 종료)
2. 파이프가 갈 수 있는 방향은 오른쪽(➡), 오른쪽 위 대각선(↗) 오른쪽 아래 대각선(↘) 3개
3. 파이프는 한 칸 당 한 개만 설치 가능!
건물이 있으면 파이프 설치 x

 

파이프는 한 칸 당 한 개만 설치할 수 있고, 무조건 첫 번째 열에서 시작해서 마지막 열에서 종료 되어야 하기 때문에 한 개의 파이프 라인은 반드시 첫 번째 열에서 하나를 차지하고 마지막 열에서 하나를 차지함!

>> 탐색을 해갈 때 오른쪽 위 대각선(↗) , 오른쪽(➡), 오른쪽 아래 대각선(↘) 순서로 탐색

 

1. 입력 받기

오른쪽 위 대각선(↗) , 오른쪽(➡), 오른쪽 아래 대각선(↘) 순서로 탐색을 하기 때문에 방향 벡터 dr을 생성

이동을 할 때 무조건 오른쪽으로만 이동하기 때문에 컬럼 방향 벡터는 항상 1!

그래서 따로 생성하지 않음

	static int[] dr = {-1,0,1}; //우상 , 우, 우하
	
	static int R,C;
	static char[][] map;
	static boolean[][] v;
	static int ans;
	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];
		v = new boolean[R][C];
		
		for(int i=0; i<R; i++) {
			String str = br.readLine();
			for(int j=0; j<C; j++) {
				map[i][j] = str.charAt(j);
			}
		}
	}

 

2. 파이프 라인 설치하기 - dfs

현재 칸에 파이프를 설치 했다고 체크 후

방향 벡터로 3방향을 탐색하면서 가능한 방향으로 이동

• 위 과정을 반복해서 마지막 열까지 도착했다면 파이프 라인 설치가 완성된 거기 때문에 처음까지 true를 리턴
• 위 과정 중 하나라도 false가 있다면 그 길은 절대 성공할 수 없는 길이기 때문에 처음까지 false를 리턴
  • 다음 행으로 넘어가서 다시 파이프 설치 가능한지 탐색

ans = 0;
for(int i=0; i<R; i++) {
	if(v[i][0]) continue;
	if(setPipe(i,0)) ans++;
}
System.out.println(ans);

// r : 파이프 설치하는 row, cnt : 설치한 파이프 개수(= 파이프 설치하는 column)
static boolean setPipe(int r, int cnt) { 
		v[r][cnt] = true; // 해당 칸에 파이프 설치 체크

		// 설치한 파이프 개수가 C-1이면(파이프 설치하는 column이 C-1이면)
		if(cnt == C-1) return true; 
		
		for(int d=0; d<3; d++) {
			int ni = r + dr[d];
			int nj = cnt + 1;
			
			// 범위를 벗어나지 않고, 아직 파이프가 설치 되어 있지 않고 다음 설치할 칸에 건물이 없으면
			if(0<=ni&&ni<R && nj<C && !v[ni][nj] && map[ni][nj] != 'x') {
				if(setPipe(ni, nj)) return true;
			}
		}
		return false;
}

 

3. 전체 코드

package boj_0221;

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

public class B3109 {
	static int[] dr = {-1,0,1}; //우상 , 우, 우하
	
	static int R,C;
	static char[][] map;
	static boolean[][] v;
	static int ans;
	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];
		v = new boolean[R][C];
		
		for(int i=0; i<R; i++) {
			String str = br.readLine();
			for(int j=0; j<C; j++) {
				map[i][j] = str.charAt(j);
			}
		}
		
		ans = 0;
		for(int i=0; i<R; i++) {
			if(v[i][0]) continue;
			if(setPipe(i,0)) ans++;
		}
		System.out.println(ans);
	}
	
	static boolean setPipe(int r, int cnt) {
		v[r][cnt] = true;
		if(cnt == C-1) return true;
		
		for(int d=0; d<3; d++) {
			int ni = r + dr[d];
			int nj = cnt + 1;
			
			// 범위를 벗어나지 않고, 아직 파이프가 설치 되어 있지 않고 다음 설치할 칸에 건물이 없으면
			if(0<=ni&&ni<R && nj<C && !v[ni][nj] && map[ni][nj] != 'x') {
				if(setPipe(ni, nj)) return true;
			}
		}
		return false;
	}
}