[백준] 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;
}
}
}
Author And Source
이 문제에 관하여([백준] 14712번 넴모넴모(Easy) - Java, 자바), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmjieun/백준-14712번-넴모넴모Easy-Java-자바저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)