Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Baaaaaaaaaduk2 (Easy)
- #include <stdio.h>
- #include <stdlib.h>
- #include <stdbool.h>
- int arr[21][21] = {0,}; // 처음 입력받은 Map 배열(바둑판)
- int cal[21][21] = {0,}; // 따로 착수를 하려는 Map 배열(바둑판)
- bool queCheck[21][21] = {false,}; // DFS로 지금 위치의 흑돌이 살아있는 흑돌인지 죽어있는 흑돌인지 판단할 때 사용할 배열
- bool Catch[21][21] = {false,}; // 기본적으로 false로 초기화하고 흑돌 위치인데 false면 살아있는 흑돌, true면 죽은 흑돌, 우리가 점수로 계산할 흑돌이라는 뜻
- int dir_x[4] = {-1, 0, 1, 0}; // 상, 하, 좌, 우 계산하려고 만듬.
- int dir_y[4] = {0, 1, 0, -1};
- bool check(int x, int y, int N, int M){ // 해당 포지션이 바운더리를 넘어갔는지 안 넘어 갔는지 체크하는 함수
- if( x<0 || y<0 || x>=N || y>=M ){
- return false;
- }else{
- return true;
- }
- }
- void Dfs(int x, int y, int N, int M){ // 해당 흑돌이 살아있는지 안 살아있는지 인접한 모든 흑돌의 상태를 체크해보고 지금 자신의 흑돌의 상태를 판별할 수 있다.
- // 해당 그룹에 단 하나의 흑돌이라도 살아있으면 그 그룹 전체의 흑돌은 살아있다.
- int i;
- int dx, dy;
- bool flag = false;
- queCheck[x][y] = true; // DFS할때 visited[v]하는 배열처럼
- for(i=0;i<4;i++){
- dx = x+dir_x[i];
- dy = y+dir_y[i];
- if(check(dx, dy, N, M)){ // 해당 좌표가 바둑판을 벗어나지 않으면서,
- // 지금 이 흑돌과 상,하,좌,우로 연결된 어떠한 흑돌이라도 살아있으면 나머지 방향은 검사할 필요도 없음. 살아있음이 보장됐기 때문에.
- if(cal[dx][dy] == 2 && Catch[dx][dy] == false && queCheck[dx][dy] == false){
- flag = true;
- break;
- }else;
- }else;
- }
- if(flag == true){ // 이 돌은 살아있음.
- Catch[x][y] = false;
- return ;
- }
- for(i=0;i<4;i++){ // 지금 이 돌이 죽었는지 살았는지 정확하게 몰라 == 빈 공간과 인접하진 않고 흑돌과 인접한 경우, 인접한 흑돌도 검사해야댐.
- dx = x+dir_x[i];
- dy = y+dir_y[i];
- if(check(dx, dy, N, M)){ // 바둑판 좌표 내에 존재하고, 인접한 흑돌이고, 그 인접한 흑돌이 아직 검사하지 않은 상태면 검사.
- if(cal[dx][dy] == 2 && Catch[dx][dy] == true && queCheck[dx][dy] == false){
- Dfs(dx, dy, N, M);
- }else;
- }else;
- }
- }
- int main()
- {
- bool flag = true;
- int N, M;
- int i, j, k, l, m;
- int dx, dy;
- int cnt = 0; // 검색할 좌표가 몇 개인지
- int sum = 0; // 착수한 Case마다 잡을 수 있던 흑돌의 최대 개수
- int max = 0; // 정답
- int pos[2][1601] = {0,}; // 런타임에러가 발생했던 이유, 우리가 착수할 수 있는 모든 좌표를 여기에 담으려고 했는데 구하는 과정에서 중복이 포함되게 설정해놨다. 그래서 401개에서 커버가 되는 것이 아니라 1601개 까지 할당했음.
- // 초기화
- for(i=0;i<20;i++){
- for(j=0;j<20;j++){
- arr[i][j] = 0;
- cal[i][j] = 0;
- Catch[i][j] = false;
- queCheck[i][j] = false;
- }
- }
- for(i=0;i<2;i++){
- for(j=0;j<1601;j++){ // 정답 제출했을땐 401로 해서 통과됐으나 정확히는 1601로 바꿔줘야 쓰레기값을 대비할 수 있음.
- pos[i][j] = 0;
- }
- }
- scanf("%d %d", &N, &M);
- for(i=0;i<N;i++){
- for(j=0;j<M;j++){
- scanf("%d", &arr[i][j]);
- cal[i][j] = arr[i][j];
- }
- }
- dx = 0;
- dy = 0;
- for(i=0;i<N;i++){
- for(j=0;j<M;j++){
- if(arr[i][j] == 2){ // 바둑판에서 흑돌을 찾았음.
- for(k=0;k<4;k++){
- dx = i+dir_x[k];
- dy = j+dir_y[k];
- if(check(dx, dy, N, M)){
- if(arr[dx][dy] == 0){ // 그 흑돌과 상, 하, 좌, 우로 인접한 빈 공간(0)을 찾음 == 우리가 착수할 가능성이 있는 공간
- pos[0][cnt] = dx; // 같은 좌표가 상,하,좌,우에 검사하면서 최대 4번까지 중복될 수 있기 때문에, 3번문제가 1000X1000사이즈 바둑판이니까 중복처리를 해줘야 될 듯.
- pos[1][cnt] = dy;
- cnt++;
- }else;
- }else;
- }
- }
- }
- }
- dx = dy = 0;
- for(i=0;i<cnt-1;i++){
- for(j=i+1;j<cnt;j++){
- cal[pos[0][i]][pos[1][i]] = 1; // 가능한 좌표에 돌 하나를 착수함.
- cal[pos[0][j]][pos[1][j]] = 1; // 가능한 좌표에 돌 하나를 착수함.
- for(k=0;k<N;k++){
- for(l=0;l<M;l++){
- if(cal[k][l] == 2){ // 흑돌을 발견했다.
- flag = true;
- for(m=0;m<4;m++){
- dx = k+dir_x[m];
- dy = l+dir_y[m];
- if(check(dx, dy, N, M)){
- if(cal[dx][dy] == 0){ // 그 흑돌 근처에 빈 공간이 있다 == 그 흑돌은 살았다. == 다른 좌표 검사할 필요없이 이 흑돌은 살아있음이 보장됀다.
- flag = false;
- }else;
- }else;
- if(!flag){
- Catch[k][l] = false; // 이 흑돌은 살아있다. 잡아먹을 수 없는 흑돌이다.
- break;
- }
- }
- if(flag){ // 상,하,좌,우를 다 검사해봤는데 인접한 빈 공간이 없다. 이 흑돌은 죽어있다. 먹을 수 있는 흑돌이다.
- Catch[k][l] = true;
- }
- }
- }
- }
- // 초기화
- for(k=0;k<N;k++){
- for(l=0;l<M;l++){
- queCheck[k][l] = false;
- }
- }
- flag = true;
- for(k=0;k<N;k++){
- for(l=0;l<M;l++){
- if(Catch[k][l] == true && cal[k][l] == 2){ // 위에서 1차적으로 검사했을 땐 인접한 상,하,좌,우가 빈 공간이 있냐, 없냐를 기준으로 살아있냐 죽어있냐를 판단했음.
- Dfs(k, l, N, M); // 위에선 인접한 돌이 흑돌인 경우에 그 흑돌이 살아있는지 죽어있는지에 따라 이 돌이 살아있냐 죽어있냐를 알 수 있는데, 인접한 모든 흑돌을 검사해야 하기 때문에 DFS사용
- for(m=0;m<4;m++){ // DFS 끝나고 맨 처음 DFS 호출했던 그 위치도 최신화를 해줘야 되서 한 번 더 돌려줌 -> 구현문제임
- dx = k+dir_x[m];
- dy = l+dir_y[m];
- if(check(dx, dy, N, M)){
- if(cal[dx][dy] == 2 && Catch[dx][dy] == false){
- flag = false;
- }else;
- }else;
- }
- if(flag == false){
- Catch[k][l] = false;
- }
- }
- flag = true;
- }
- }
- sum = 0;
- for(k=0;k<N;k++){
- for(l=0;l<M;l++){
- if(Catch[k][l] == true){ // 잡아 먹을 수 있는 돌의 개수 계산
- sum++;
- }
- }
- }
- // 초기화
- for(k=0;k<N;k++){
- for(l=0;l<M;l++){
- Catch[k][l] = false;
- queCheck[k][l] = false;
- }
- }
- max = max>sum?max:sum;
- sum = 0;
- cal[pos[0][i]][pos[1][i]] = 0;
- cal[pos[0][j]][pos[1][j]] = 0;
- }
- }
- printf("%d", max);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement