구름톤 챌린지 3주 차 문제 13 학습 일기

https://goor.me/wDFSjuDNjzXTTqH4A

​

 

 

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

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int [][]map = new int[N][N];
		int []ans = new int [32];
		
		Queue<Node> q = new LinkedList<>();
			
		int []dx = {-1, 1, 0, 0};
		int []dy = {0, 0, -1, 1};
		
		for(int i = 0; i <N; i++){
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++){
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int max = 0;
		int res = 0;
		
		for(int i = 0; i <N; i++){
			for(int j = 0; j < N; j++){
				int cnt = 0;
				if(map[i][j] != 0){
					cnt++;
					q.add(new Node(i, j));
					int num = map[i][j];
					map[i][j] = 0;
					while(!q.isEmpty()){
						Node node = q.poll();
						for(int k = 0; k <4; k++){
							int newi = node.i + dx[k];
							int newj = node.j + dy[k];
							if(newi >=0 && newi < N && newj >=0 && newj < N && map[newi][newj] == num){
								cnt++;
								q.add(new Node(newi, newj));
								map[newi][newj] = 0;
							}
						}
					}
					if (cnt >= K){
						ans[num] ++;
					}
				}
			}
		}
		for(int i =0; i<32; i++){
			if (ans[i] >= max){
				max = ans[i];
				res = i;
			}
		}
		System.out.println(res);
	}
}

class Node{
	int i;
	int j;
	
	Node(int i, int j){
		this.i = i;
		this.j = j;
	}
}

탐색 문제이다. bfs로 풀었다.

백준 10026 적록색약 문제와 유형이 비슷하다.

같은 정수가 상하 좌우로 k개 이상 인접해있다면 1개의 단지로 볼 수 있는데, 단지가 가장 많은 정수를 출력하면 된다.

​

같은 수가 3개 이상 인접해있다면 단지로 볼 수 있다면

​

1 1 1 2

2 2 1 3

1 1 3 3

​

이 예시에서는 1단지 1개 2단지 0개 3단지 1개 이다.

탐색을 통해 인접 행렬을 탐색하고 같은 수가 k개 이상 붙어있다면 단지의 수를 1개 늘려주면 된다.

주의해야할 점이 있다면 단지의 갯수만 따져야한다. 단지 + 숫자의 갯수까지 따지면 안된다.

예를 들어

​

1 1 1 1 1

1 1 1 1 3

1 1 1 3 3

3 3 3 1 1

​

이런 예시가 있다면 1단지 1개 3단지 2개로 3을 출력해야 한다. 1이 많다고 출력하면 안된다.

그리고 이거 리뷰 쓰면 네이버 포인트 5000원 준다.