https://www.acmicpc.net/problem/16988
16988번: Baaaaaaaaaduk2 (Easy)
서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의
www.acmicpc.net
코드설명
DFS(깊이우선탐색) + BFS(너비우선탐색) + 조합(Combination) 을 활용하는 문제입니다
먼저 DFS로 바둑을 둘 곳을 조합으로 구하고, 모든 바둑을 둔 뒤에는 BFS로 몇개의 바둑이 죽는지 확인하면 되는 문제입니다.
좀 더 시간복잡도를 낮게 하고싶다면, 죽을 수 있는 검은 돌만 따로 계산하여 진행하는 방법도 있습니다.
처음에 실패했던 점은,
5 4
0 0 0 0
0 2 2 0
0 2 0 0
2 2 0 0
2 2 0 0
----
0 0 0 0
0 2 2 0
1 2 0 0
2 2 0 0
2 2 1 0
정답 : 0
오답 : 3
아래와 같은 예제에서 답이 3 이 나옵니다.
이유는 (4, 0)에서 이미 방문한 곳을 visited 처리되며 해당 칸을 아예 가지않게 되기 떄문입니다.
좀더 자세히보면, (3, 0) -> (4, 0) -> (4, 1) 로 이동하기 떄문입니다.
이렇게 되면 안되므로 다른 방법을 찾아보았습니다.
처음 코드의 문제점은 만약 0 이라면 바로 종료시키는 것이 문제였습니다.
위의 로직을 변경하여 만약 해당 BFS 그룹에서 0 을 만난다면 해당 검은 그룹은 죽을 수 없는 그룹으로 연산하고, 해당 그룹을 방문처리합니다.
if(map[nr][nc] == 0) deadFlag = true;
// if(map[nr][nc] == 0) return 0;그를 위해 deadFlag = false 일때만 죽을 수 있도록 처리하고,
visited 처리를 하여 해당 그룹을 더 이상 방문하지 않도록 해줍니다.
이러한 개선을 통해 visited[][]는 오직 BFS 내에서 해당 바둑을 탐색하는데에만 사용해야한다는 것을 생각하게 되었습니다. 처음에는 불필요하게, 만약 '0' 을 만났을경우 바둑이 자유로운 경우이므로 이후에 탐색이 안되도록 처리하려고 했지만, 원래 의도한 visited에 불필요 연산이 추가되면서 독립적인 연산을 보장하지 못하게 되었습니다.
visited 검사 연산을 앞부분에 넣는 방향으로 순서를 바꾸어도 괜찮겠지만, 독립적인 방문배열을 처리하는 것을 유의해야한다고 느꼈습니다. .
if(map[nr][nc] == 0) {
flag = false; // 못먹는 부분일경우 처리합니다.
// visited[nr][nc] = true; //0 일경우 방문처리하고 넘어갈경우, 다른 곳에서 해당 칸이 0 임에도 제대로 작동하지 못하여 먹힌 바둑으로 생각하는 문제가 있다.
// return 0; //만약 return 0 로 할경우, 해당 부분이 이미 시작할떄 visited로 칠해지니 다른 부분이 이곳을 오지 못하게 되어 count가 올바르지않다.
// 해당 그룹을 모두 돌면서 더이상 이 그룹을 아무도 연산하지 못하게 해야한다.
continue;
}
또한 DFS로 Map을 도는 방안이 2가지가 존재합니다.
1. 직접 위치를 보내는 방안의 경우
public static void simulate(int level, int r, int c, int whiteCnt) {
if(c >= M) {
r = r + 1;
c = 0;
}
if(whiteCnt == 2) {
visited = new boolean[N][M];
int deadCnt = 0;
for(int i=0;i<black.size();i++) {
Node temp = black.get(i);
if(visited[temp.r][temp.c] == false ) {
deadCnt += checkDeadBFS(temp.r, temp.c);
}
}
answer = Math.max(answer, deadCnt);
return ;
}
if(r >= N) {
return ;
}
//흰색 바둑을 두는경우
if(map[r][c] == 0) {
map[r][c] = 1;
simulate(level + 1, r, c + 1, whiteCnt + 1);
map[r][c] = 0;
}
//그냥 넘어가는 경우
simulate(level + 1, r, c + 1, whiteCnt);
}
2. For문으로 처리하는 경우
public static void simulate(int level, int r, int c, int whiteCnt) {
if(whiteCnt == 2) {
visited = new boolean[N][M];
int deadCnt = 0;
for(int i=0;i<black.size();i++) {
Node temp = black.get(i);
if(visited[temp.r][temp.c] == false ) {
deadCnt += checkDeadBFS(temp.r, temp.c);
}
}
answer = Math.max(answer, deadCnt);
return ;
}
for(int i=r; i<N;i++) {
for(int j= (i == r ? c : 0); j<M; j++) {
//흰색 바둑을 두는경우
if(map[i][j] == 0) {
map[i][j] = 1;
simulate(level + 1, i, j + 1, whiteCnt + 1);
map[i][j] = 0;
}
}
}
}
코드
수정한 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N, M;
public static long answer = 0;
public static int[] arr;
public static int[][] map;
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
public static int[] comb = new int[2];
public static int[] dx = {-1, 1, 0,0};
public static int[] dy = {0, 0, -1, 1};
public static boolean[][] visited;
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][M];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<M;j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
getComb(0, 0, 0);
System.out.println(answer);
}
public static void getComb(int level, int r, int c) {
if(level == 2) {
visited = new boolean[N][M];
int cnt =0;
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
if(map[i][j] == 2 && visited[i][j] == false) {
cnt += BFS(i, j);
answer = Math.max(answer, cnt );
}
}
}
return ;
}
for(int i=r; i<N;i++) {
for(int j=(i == r) ? c : 0; j<M;j++) {
// comb[level] = i * N + j;
//만약 0 이라면 바둑을 둔다.
if(map[i][j] == 0) {
map[i][j] = 1;
getComb(level + 1, i, j);
map[i][j] = 0;
}
}
}
}
public static int BFS(int r, int c) {
Queue<Node> q = new LinkedList<>();
q.offer(new Node(r, c, 1));
visited[r][c] = true;
int result = 1;
boolean deadFlag = false;
while(!q.isEmpty()) {
Node temp = q.poll();
for(int dir = 0; dir < 4; dir++) {
int nr = temp.r + dx[dir];
int nc = temp.c + dy[dir];
if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
if(visited[nr][nc] == true) continue;
if(map[nr][nc] == 1) continue ;
if(map[nr][nc] == 0) deadFlag = true;
// if(map[nr][nc] == 0) return 0;
if(map[nr][nc] == 2) {
result += 1;
visited[nr][nc] = true;
q.offer(new Node(nr, nc, temp.cnt + 1));
}
}
}
if(deadFlag == false) {
return result;
}
return 0;
}
}
class Node{
int r;
int c;
int cnt;
public Node(int r, int c, int cnt) {
this.r=r;
this.c=c;
this.cnt = cnt;
}
}
직접 모든위치를 순회한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N, M;
public static int[][] map;
public static int answer = 0;
public static ArrayList<Node> black = new ArrayList<Node>();
public static boolean[][] visited;
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][M];
// 0 : 빈칸, 1 : 나의 돌, 2 : 상대의 돌
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<M;j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j] == 2) {
black.add(new Node(i, j));
}
}
}
simulate(0, 0, 0, 0);
System.out.println(answer);
}
public static void simulate(int level, int r, int c, int whiteCnt) {
if(c >= M) {
r = r + 1;
c = 0;
}
if(whiteCnt == 2) {
visited = new boolean[N][M];
int deadCnt = 0;
for(int i=0;i<black.size();i++) {
Node temp = black.get(i);
if(visited[temp.r][temp.c] == false ) {
deadCnt += checkDeadBFS(temp.r, temp.c);
}
}
answer = Math.max(answer, deadCnt);
return ;
}
if(r >= N) {
return ;
}
//흰색 바둑을 두는경우
if(map[r][c] == 0) {
map[r][c] = 1;
simulate(level + 1, r, c + 1, whiteCnt + 1);
map[r][c] = 0;
}
//그냥 넘어가는 경우
simulate(level + 1, r, c + 1, whiteCnt);
}
public static int checkDeadBFS(int startR, int startC) {
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
int count = 1;
Queue<Node> q = new LinkedList<>();
boolean flag = true; //기본적으로는 먹을 수 있다고 가정합니다.
visited[startR][startC] = true;
q.offer(new Node(startR, startC));
while(!q.isEmpty()) {
Node temp = q.poll();
int r = temp.r;
int c = temp.c;
for(int dir = 0; dir < 4; dir++) {
int nr = r + dx[dir];
int nc = c + dy[dir];
//만약 범위 밖으로 나간다면, continue
if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
if(map[nr][nc] == 1) continue; //만약 이미 하얀돌일경우 continue.
if(visited[nr][nc] == true) continue;
//만약 범위밖으로 나간다면, 해당 부분은 못먹는 부분이다.
if(map[nr][nc] == 0) {
flag = false; // 못먹는 부분일경우 처리합니다.
// visited[nr][nc] = true; //왜 nr, nc 가 true일경우 안될까... 0 일경우 방문처리하고 넘어갈경우, 다른 곳에서 해당 칸이 0 임에도 제대로 작동하지 못하고 더해버린다.
// return 0; //만약 return 0 로 할경우, 해당 부분이 이미 시작할떄 visited로 칠해지니 다른 부분이 이곳을 오지 못하게 되어 count가 올바르지않다.
continue;
}
count += 1;
visited[nr][nc] = true;
q.offer(new Node(nr, nc));
}
}
if(flag == true) {
return count;
}else {
return 0;
}
}
}
class Node{
int r;
int c;
public Node(int r, int c) {
this.r=r;
this.c=c;
}
}
처음에 BFS를 진행하여 틀린경우입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N, M;
public static long answer = 0;
public static int[] arr;
public static int[][] map;
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
public static int[] comb = new int[2];
public static int[] dx = {-1, 1, 0,0};
public static int[] dy = {0, 0, -1, 1};
public static boolean[][] visited;
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][M];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<M;j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
getComb(0, 0, 0);
System.out.println(answer);
}
public static void getComb(int level, int r, int c) {
if(level == 2) {
visited = new boolean[N][M];
int cnt =0;
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
if(map[i][j] == 2 && visited[i][j] == false) {
cnt += BFS(i, j);
answer = Math.max(answer, cnt );
}
}
}
return ;
}
for(int i=r; i<N;i++) {
for(int j=(i == r) ? c : 0; j<M;j++) {
// comb[level] = i * N + j;
//만약 0 이라면 바둑을 둔다.
if(map[i][j] == 0) {
map[i][j] = 1;
getComb(level + 1, i, j);
map[i][j] = 0;
}
}
}
}
public static int BFS(int r, int c) {
Queue<Node> q = new LinkedList<>();
q.offer(new Node(r, c, 1));
visited[r][c] = true;
int result = 1;
while(!q.isEmpty()) {
Node temp = q.poll();
for(int dir = 0; dir < 4; dir++) {
int nr = temp.r + dx[dir];
int nc = temp.c + dy[dir];
if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
if(visited[nr][nc] == true) continue;
if(map[nr][nc] == 1) continue ;
if(map[nr][nc] == 0) return 0;
if(map[nr][nc] == 2) {
result += 1;
visited[nr][nc] = true;
q.offer(new Node(nr, nc, temp.cnt + 1));
}
}
}
return result;
}
//바둑을 둔상태에서 이제 죽일 수 있는 최대개수를 구한다. 이렇게할경우 불가능하다.
// public static int simulate(int level, int r, int c) {
// if(flag == true) return 0;
// int result = 0;
// visited[r][c] = true;
// for(int dir = 0; dir < 4; dir++) {
// int nr = r + dx[dir];
// int nc = c + dy[dir];
//
// if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
// if(map[nr][nc] == 0) { //만약 빈칸을 갈 수 있다면 실패입니다.
// flag = true;
// return 0;
// }
// if(visited[nr][nc] == true) continue;
//
// if(map[nr][nc] == 2) {
// result = simulate(level + 1, nr, nc) + 1;
// }
//
// }
//
// return result;
// }
}
class Node{
int r;
int c;
int cnt;
public Node(int r, int c, int cnt) {
this.r=r;
this.c=c;
this.cnt = cnt;
}
'알고리즘 > 백준' 카테고리의 다른 글
| [백준] 27172 수 나누기 게임 - 에라토스테네스의 체 JAVA (0) | 2023.11.27 |
|---|---|
| [백준] 17090 미로 탈출하기 - DFS(깊이우선탐색) + DP(Dynamic Programming) JAVA (0) | 2023.11.27 |
| [백준] 16724 피리 부는 사나이 - DFS(깊이우선탐색) + 싸이클확인(Cycle Check) JAVA (0) | 2023.11.25 |
| [백준] 2186 문자판 - DFS(깊이우선탐색) + DP(Dynamic Programming) JAVA (0) | 2023.11.24 |
| [백준] 19236 청소년 상어 - 시뮬레이션 + 구현 + 백트래킹 JAVA (0) | 2023.11.21 |