백준 3109. 빵집

🅰 백준 3109. 빵집

3109번: 빵집

✏️ 문제 풀이

• 오른쪽으로만 가는 방향만 생각하면 된다.
• 오른쪽 위, 오른쪽, 오른쪽 아래를 탐색 후 갈 수 있으면 간 후에 지나온 길은 true로 방문 표시해준다.
• 기저조건으로 파이프가 빵집의 위치인 C-1에 도착했다면 return을 해주고 다른 케이스들이 재귀를 돌면서 추가 파이프가 생기지 않게 하기 위해 check를 true로 설정해주었다.
• 맨 윗줄, 맨 아래줄은 case를 따로 구분해 주었으며, 만약 방문하였는데 길이 막혀있다면 backtracking해서 다시 갈 수 있는 길로 가야하기 때문에 if, else if, else안에는 다 if문으로 설정을 해두고, 조건으로 check가 false이면 재귀가 수행되도록 하였다.

✏️ 소스코드

package com.ssafy.baekjoon;

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

public class Main_골드2_3109_손은성 {
	static boolean map[][];
	static int R, C, cnt;
	static boolean check;

	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 boolean[R][C];
		for (int i = 0; i < R; i++) {
			String str = br.readLine();
			for (int j = 0; j < C; j++) {
				if (str.charAt(j) == 'x') {
					map[i][j] = true;
				}
			}
		}
		for (int i = 0; i < R; i++) {
			search(i, 0);
			check = false;
		}
		System.out.println(cnt);
	}

	private static void search(int row, int col) {

		if (col == C - 1) {
			check = true; // 파이프를 설치 했을 때 backtracking시 다른 파이프 새로 못만들게 
           				//check = true로 설정
			cnt++;
			return;
		}
		if (row == 0) { // 열이 맨 위에 일 때
			if (!map[row][col + 1] && !check) { // 오른쪽 길 있을 때
				rightCheck(row, col);
			}
			if (!map[row + 1][col + 1] && !check) { // 오른쪽 아래 길 있을 때
				underRightCheck(row, col);
			}
		}

		else if (row == R - 1) { // 열이 맨 아래일 때
			if (!map[row - 1][col + 1] && !check) { // 오른쪽 위에 길 있을 때
				upRightCheck(row, col);
			}
			if (!map[row][col + 1] && !check) { // 오른쪽 길 있을 때
				rightCheck(row, col);
			}
		}

		else {
			if (!map[row - 1][col + 1] && !check) { // 오른쪽 위에 길 있을 때
				upRightCheck(row, col);
			}
			if (!map[row][col + 1] && !check) { // 오른쪽 길 있을 때
				rightCheck(row, col);
			}
			if (!map[row + 1][col + 1] && !check) { // 오른쪽 아래 길 있을 때
				underRightCheck(row, col);
			}
		}
		return;
	}

	static void rightCheck(int row, int col) {
		map[row][col + 1] = true; // 지나왔던 길 기록
		search(row, col + 1); // 오른쪽 탐색
	}

	static void upRightCheck(int row, int col) {
		map[row - 1][col + 1] = true; // 지나왔던 길 기록
		search(row - 1, col + 1); // 오른쪽 대각선 위 탐색
	}

	static void underRightCheck(int row, int col) {
		map[row + 1][col + 1] = true; // 지나왔던 길 기록
		search(row + 1, col + 1); // 오른쪽 대각선 아래 탐색
	}
}

 

✅ 후기

• 골드 2문제는 처음이라 어려웠지만 접근법을 알고 풀었을 때에도 어려웠다ㅎㅎㅎ
• 파이프가 빵집에 연결되고 난 후 return을 했을 때 함수 자체가 종료되기를 원했는데 재귀함수 특성 상 그렇게는 하지 못하고 그대신 boolean 변수를 이용하여 도착 했을 때 다른 재귀함수가 동작하지 않도록 하여서 종료해주었다.
• 다양한 해결방법이 있지만 이제서야 boolean함수를 사용하는데 조금 익숙해진 것 같다.