[백준] 14712번 넴모넴모(Easy) - Java, 자바

난이도

실버 1

문제

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

풀이

현재 위치를 아래를 이용해서 구한다.

        int y = cnt / m + 1;
        int x = cnt % m + 1;

예시) m=3
cnt = 0일 때 (1,1), 1일 때 (1,2), 2일 때 (1,3), 3일 때 (2,1), 4일 때 (2,2), 5일 때 (2,3)

현재 위치에서 위, 왼쪽, 왼쪽 대각선이 모두 1인 경우에 넴모를 두게 되면 넴모를 없앨 수 있는 경우가 나오므로 cnt를 1 증가시켜서 dfs 탐색으로 넘어간다.

현재 위치에 놓을 수 있다면, 선택을 하는 경우와 선택을 하지 않은 두가지 경우로 탐색한다.

        if (map[y - 1][x] == 1 && map[y][x - 1] == 1 && map[y - 1][x - 1] == 1) {
            // 현재 놓을 수 없는 곳
            dfs(cnt + 1);
        } else {
            dfs(cnt + 1); // 선택안하고 다음꺼 본 경우
            map[y][x] = 1;
            dfs(cnt + 1);// 선택하고 다음꺼 본 경우
            map[y][x] = 0;
        }

코드

package 백트래킹;

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

public class BOJ14712 {
    static int n, m;
    static int ans;
    static int[][] map;

    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());

        map = new int[n + 1][m + 1];

        dfs(0);
        System.out.println(ans);
    }

    static void dfs(int cnt) {
        if (cnt == n * m) {
            ans++;
            return;
        }
        int y = cnt / m + 1;
        int x = cnt % m + 1;

        if (map[y - 1][x] == 1 && map[y][x - 1] == 1 && map[y - 1][x - 1] == 1) {
            // 현재 놓을 수 없는 곳
            dfs(cnt + 1);
        } else {
            dfs(cnt + 1); // 선택안하고 다음꺼 본 경우
            map[y][x] = 1;
            dfs(cnt + 1);// 선택하고 다음꺼 본 경우
            map[y][x] = 0;
        }

    }
}