[BOJ] 백준 2667번 - 단지번호 붙이기 (Python)

문제

문제 바로가기

해결

문제를 보면 직관적으로 풀이 방법이 떠오른다.

1. 그래프에서 ‘1’인 곳의 인덱스를 찾는다.
2. BFS/DFS를 사용하여 연속된 ‘1’을 탐색해나가며 ‘1’을 다른 임의의 값으로 바꾸어가며 카운트를 센다.
3. 카운트가 끝나면 아파트 단지 리스트에 카운트(집의 개수)를 추가한다.
4. 1번에서 ‘1’인 곳이 존재하지 않을 때까지 반복한다.

첫 번째 제출

파이썬으로 작성한 첫 번째 제출답안은 다음과 같다.

import sys
from collections import deque

n = int(input())
map = []
village = []

for _ in range(n):
    line = sys.stdin.readline().rstrip()
    map.append(line)

# 북동남서 (시계방향)
move_n = [-1, 0, 1, 0]
move_m = [0, 1, 0, -1]

def detect_house(map):
    for i in range(n):
        for j in range(n):
            if map[i][j] == '1':
                return (i, j)
    return None
    
def count_house(map, row, col):
    cnt = 0
    q = deque()
    q.append((row, col))

    while q:
        y, x = q.popleft()
        if map[y][x] == '1':
            map[y] = list(map[y])
            map[y][x] = '2'
            map[y]=''.join(map[y])
            cnt += 1
        
        for i in range(4):
            ny = y + move_n[i]
            nx = x + move_m[i]

            if ny >= n or nx >= n or ny < 0 or nx < 0:
                continue
            elif map[ny][nx] != '1':
                continue
            else:
                q.append((ny, nx))
    return cnt

while detect_house(map) != None:
    y, x = detect_house(map)
    village.append(count_house(map, y, x))

village.sort()
print(len(village))
for v in village:
    print(v)

하지만 해당 답안은 잘 굴러가다가.. 메모리 초과가 떴다. 많은 반복문을 돌렸기 때문에 시간 초과가 날지 모른다는 생각은 했는데, 메모리 초과는 생각하지 못했다.

내가 선언한 변수들은 village, map, line, move_n, move_m, ny, nx, y, x... 뭔가 많이 선언한 것 같지는 않은데… 그래도 일단 최대한 사용하지 않아도 될 걸 천천히 빼보았다..

그리고 행의 변화를 x로 열의 변화를 y로 바꾸었다 대부분의 코드가 이런 식으로 작성되어 있었기에 아무래도 익숙해지기 전에 바꾸는 것이 좋아보였다.

두 번째 제출

from collections import deque

# 동서남북
move_x = [0, 0, 1, -1]
move_y = [1, -1, 0, 0]
    
def count_house(m, a, b):
    n = len(m)
    q = deque()
    q.append((a, b))
    m[a][b] = 0
    cnt = 1

    while q:
        x, y = q.popleft()
        
        for i in range(4):
            nx = x + move_x[i]
            ny = y + move_y[i]

            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue

            if m[nx][ny] == 1:
                m[nx][ny] = 0
                q.append((nx, ny))
                cnt += 1
    return cnt

n = int(input())
city_map = []

for _ in range(n):
    city_map.append(list(map(int, input())))

village = []
for i in range(n):
    for j in range(n):
        if city_map[i][j] == 1:
            village.append(count_house(city_map, i, j))

village.sort()
print(len(village))
for v in village:
    print(v)

line을 없애고 바로바로 append() 함수를 사용하였고, ‘1’인 인덱스를 찾아 반환하는 함수도 삭제하였다. 또한 list(map(int, input()))을 사용하여 리스트가 한 숫자씩 요소를 담도록 했다. 따라서 리스트로 변환하는 과정도 삭제하였다.

그리고 가장 중요한 것.. map이라는 변수를 사용했다는 것이다. map은 원래 기본 라이브러리 함수인데,, 분명 알고있는데 이런 실수를 저질러 버렸다.

결과는 맞았습니다 !!