[코드트리 챌린지] 4주차

이번주 실력진단에서는 배열에 들어갈 수를 입력받는 것에서 막혔다. 

단순히 배열 전체에 입력받는 것이 아닌 특정 위치에 답이 들어가야 하는 경우를 잘 연습해야겠다.

 

문제

 

최소 마을의 크기

import java.io.*;
import java.util.*;
import java.math.*;

public class Main {

    static class pair{
        int x;
        int y;

        pair(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    


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

        int[][] arr = new int[n][n];

        int[][] vis = new int[n][n];

        int[][] d = new int[n][n];


        StringTokenizer st;

        for(int i = 0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0;j<n;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        Stack<pair> s = new Stack<>();

        int nn = 1;

        int[] dx = {0,0,1,-1};
        int[] dy = {1,-1,0,0};

        int kk = 0;

        int min = n*n+1;

          for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
               if(vis[i][j] == 0){

                int cnt = 0;

                s.push(new pair(i,j));
                kk = arr[i][j];

                while(s.isEmpty() != true){
                    
                    pair now = s.pop();

                    d[now.x][now.y] = nn;
                    if(vis[now.x][now.y] == 0) cnt++;

                    vis[now.x][now.y] = 1;

                    for(int z = 0;z<4;z++){
                        //System.out.println(z);
                        if((now.x + dx[z]) >= 0 && (now.x + dx[z]) < n && (now.y + dy[z]) >= 0 && (now.y + dy[z]) < n && 
                        arr[now.x + dx[z]][now.y + dy[z]] == kk && vis[now.x + dx[z]][now.y + dy[z]] == 0 ){
                            s.push(new pair(now.x + dx[z],now.y + dy[z]));
                        
                        }
                    }

                }

                //System.out.println(cnt);
                 min = Math.min(cnt, min);
               }
              
            }
        }


       System.out.println(min);

        


        
        
    }
}

이 문제는 이전에 나왔던 dfs문제와 다르게 같은 부족(같은 숫자)를 가진 배열들끼리 같은 마을이 될 수 있다는 조건이 있었다. 그래서 for문을 이용하여 vis 가 0인 인덱스를 발견하면 kk변수에 해당 arr값을 넣었고, dfs할 때 stack에 들어가는 조건이 kk와 같을 때를 기준으로 하였다.

 

cnt를 세는 과정에서 오류가 발생했었는데, 이는 stack에 수를 넣는 과정에서 cnt값을 올려주는 바람에 발생하였다. stack에서 pop했을 때 해당 위치의 vis값이 0일 때에만 값을 갱신하니 정답이 나왔다.