[Python] [백준] 2667 단지번호 붙이기

파이썬으로 언어를 전환하려고한다? 

그렇다면 제일 먼저 풀어봐야하는 문제는 이 문제라고 자신한다.

코딩테스트하면 떠오르는 아주 대표적인 BFS 문제!

 

 

문제: https://www.acmicpc.net/problem/2667 

풀이: 

1. 입력을 받는다.

2. 행렬을 쭉 순회하다가 1이 나오면 bfs 를 이용해 해당 그룹이 몇개의 칸을 차지하고 있는지 센다.

3. bfs 가 끝나면 다시 행렬을 순회한다. 이때 visited 를 이용해 이전 그룹에서 해당 칸을 방문했으면 넘어간다. 

4. 각 그룹이 차지하는 칸의 개수 오름차순으로 정렬해서 반환한다. (중요!)

from collections import deque
import sys
input = sys.stdin.readline  # python의 인풋 속도향상을 위한 코드

visited = [[0] * 26 for _ in range(26)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


# 3. bfs를 이용해 각 집단에 속하는 블록의 개수를 구한다.
def bfs(i, j, m, n):
    q = deque()
    q.append([i, j])
    visited[i][j] = 1

    cnt = 0
    while q:
        x, y = q.popleft()
        cnt += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and m[nx][ny] == '1' and visited[nx][ny] == 0:
                q.append([nx, ny])
                visited[nx][ny] = 1

    return cnt

def main():
    # 1. 입력을 받아서 행렬 m을 생성한다.
    n = int(input())

    m = ['' for _ in range(n)]  # 1차원배열 초기화
    for i in range(n):  # range(n) 은 range(0, n) 과 동일하다
        m[i] = input()

    # 2. 행렬을 탐색한다.

    group = 0
    answer = []
    for i in range(n):
        for j in range(n):
            if m[i][j] == '1' and visited[i][j] == 0:
                group += 1
                cnt = bfs(i, j, m, n)
                answer.append(cnt)

    answer.sort()
    print(group)
    print(*answer, sep='\n') # * : 파이썬의 unpacking operator
 
main()

 

 

위 코드를 C++ 로 다시 작성하면 아래와 같다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;
int m[26][26];
int visited[26][26];
int n;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int bfs(int i, int j) {
	queue<pair<int, int>> q;
	q.push({ i,j });
	visited[i][j] = 1;
	int cnt = 0;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		cnt++;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 > nx || nx >= n || 0 > ny || ny >= n) continue;
			if (m[nx][ny] == 1 && visited[nx][ny] == 0) {
				q.push({ nx,ny });
				visited[nx][ny] = 1;
			}
		}
	}
	return cnt;
 
}
int main() {
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%1d", &m[i][j]);
		}
	}

	int group = 0;
	vector<int> answer;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (m[i][j] == 1 && visited[i][j] == 0) {
				group++;
				int temp = bfs(i, j);
				answer.push_back(temp);
			}
		}
	}

	sort(answer.begin(), answer.end());
	printf("%d\n", group);
	for (int i = 0; i < answer.size(); i++) {
		printf("%d\n", answer[i]);
	}
}

이상하다.. python 이 더 짧다고 생각했는데 코드 길이가 길게 나오는군. 아 주석이 있어서 그런가?

그런데 역시 파이썬은 C++ 에 비해 상대적으로 메모리랑 시간을 더 많이 차지하는군!

 

 

아래는 파이썬 코드에서 주석을 제거하고 제출했을 때의 결과다.