[백준/java] 14712. 넴모넴모(Easy)

문제 링크 - https://www.acmicpc.net/problem/14712

🌱 문제

🌱 풀이

주어진 조건에서 1 ≤ N, M ≤ 25, 1 ≤ N × M ≤ 25 이므로 NxM 배열의 각 칸에 네모가 존재할 때, 하지 않을 때로 나눠서 전부 재귀로 돌아도 충분하다고 생각했다.
네모가 있는칸을 1이라고 하고 없는 칸을 0이라고 하자
N*M 배열의 각 칸이 1인경우와 0인경우 모든경우에 넴모가 존재하는지 확인한다.
자세한 풀이는 주석에 적었다 .!!

헷갈렸던 부분

재귀함수에서 리턴하는 조건을 어떻게 쓸지가 조금 까다로웠다.
왜냐하면 배열의 마지막 칸일 때, arr[n-1][m-1] 해당 칸이 1일때와 0일때의 경우를 모두 확인하고 리턴해야 하기 때문이다. 그래서 그냥 코드와 같이 0일때, 1일때 나눠서 각각의 경우에 네모인지 확인해 주었다.

if (r == n - 1 && c == m - 1) { // 마지막 좌표인경우 
			arr[n - 1][m - 1] = 0; // 마지막 좌표가 0인경우에 답 계산하고, 1인경우에 답 계산 
			if (isNemo() == false)
				answer++;

			arr[n - 1][m - 1] = 1;
			if (isNemo() == false)
				answer++;
			return;

🌱 코드

package Sep_week03;

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

//14712. 넴모넴모 
//네모가 있는칸을 1이라고 하고 없는 칸을 0이라고 하자 
// N*M 배열의 각 칸이 1인경우와 0인경우 모든경우에 넴모가 존재하는지 확인한다. 

public class boj_14712 {
	static int n, m;
	static int answer;
	static int arr[][];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		arr = new int[n][m];
		func(0, 0);// r,c (0,0)부터 시작 
		System.out.println(answer);

	}

	public static void func(int r, int c) {  //재귀 함수 

		if (r == n - 1 && c == m - 1) { // 마지막 좌표인경우 
			arr[n - 1][m - 1] = 0; // 마지막 좌표가 0인경우에 답 계산하고, 1인경우에 답 계산 
			if (isNemo() == false)
				answer++;

			arr[n - 1][m - 1] = 1;
			if (isNemo() == false)
				answer++;
			return;
		}

		arr[r][c] = 1; //해당 칸에 네모가 존재한다고 가정 
		if (c == m - 1) // 마지막 열이면 다음 행으로 넘겨준다 (열은 0번째 됨) 
			func(r + 1, 0);
		else //  마지막 열이 아니면 열만 한칸 증가시킨다. 
			func(r, c + 1);

		arr[r][c] = 0;//해당 칸에 네모가 존재하지 않는다고 가정 
		if (c == m - 1)
			func(r + 1, 0);
		else
			func(r, c + 1);

	}

	public static boolean isNemo() { // 네모가 존재하는지 확인하는  함수 
		for (int i = 0; i < n - 1; i++) {
			for (int j = 0; j < m - 1; j++) {
				if (arr[i][j] == 1 && arr[i + 1][j] == 1 && arr[i][j + 1] == 1 && arr[i + 1][j + 1] == 1)
					return true;

			}
		}
		return false;
	}

}