Problem

문제 설명

(건물 유형별 단지의 개수, 건물 유형 번호)를 기준으로 내림차순했을 때 첫 번째 요소의 건물 유형 번호를 출력한다.

• 건물 유형별 단지는 2차원 배열에 번호가 같은 건물이 K개 이상 붙어있는 구역이다.
• 하나의 단지 내 건물들은 서로 상하좌우 인접한 칸에 위치한다.

Submitted Code

Python

 1 N, K = map(int, input().split())
 2 
 3 max_M = 0
 4 maps = [[0] * N for _ in range(N)]
 5 for i in range(N):
 6     row = list(map(int, input().split()))
 7     max_row = 0
 8     for j in range(N):
 9         maps[i][j] = row[j]
10         max_row = max(max_row, row[j])
11     max_M = max(max_M, max_row)
12
13 stack = []
14 groups = {i + 1: 0 for i in range(max_M)}
15 plant = (0, 0)
16 dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
17 for i in range(N):
18     for j in range(N):
19         M, maps[i][j] = maps[i][j], 0
20         if M == 0:
21            continue
22
23         cnt = 0
24         stack.append((i, j))
25         while stack:
26             y, x = stack.pop()
27             cnt += 1
28             for dy, dx in dirs:
29                 ny, nx = y + dy, x + dx
30                 if ny in (-1, N) or nx in (-1, N) or maps[ny][nx] == 0:
31                     continue
32                 if maps[ny][nx] == M:
33                     stack.append((ny, nx))
34                     maps[ny][nx] = 0
35         if cnt >= K:
36             groups[M] += 1
37             plant = max(plant, (groups[M], M))
38
39 print(plant[1])

C++

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
int main() {
	int N, K;
	cin >> N >> K;
	
	int maps[1000][1000] = {};
	int max_M = 0;
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			int tmp;
			cin >> tmp;
			maps[i][j] = tmp;
			max_M = max(max_M, tmp);
		}
	}
	
	stack<pair<int, int>> stack;
	int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	int groups[31] = {};
	pair<int, int> plant(0, 0);
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			int M = maps[i][j];
			maps[i][j] = 0;
			if (M == 0) continue;
			stack.push(make_pair(i, j));
			int cnt = 0;
			
			while (stack.size()){
				pair<int, int> pos(stack.top().first, stack.top().second);
				stack.pop();
				cnt++;
				for (int k = 0; k < 4; k++){
					pair<int, int> npos(pos.first + dirs[k][0], pos.second + dirs[k][1]);
					if (npos.first < 0 || npos.first >= N || npos.second < 0 || npos.second >= N)
						continue;
					
					int Mrc = maps[npos.first][npos.second];
					if (Mrc == 0) continue;
					else if (Mrc == M){
						stack.push(npos);
						maps[npos.first][npos.second] = 0;
					}		
				}
			}
			
			if (cnt >= K){
				groups[M]++;
				plant = max(plant, make_pair(groups[M], M));
			}			
		}
	}
	cout << plant.second;
	return 0;
}

Challenge Review

Python이 3초 걸린 문제를 C++에서는 0.03초 걸리는 걸 확인했다. 확실히 C++이 빠르네.