[알고리즘 연습]-단지번호붙이기(python)

1. 문제링크

[단지번호붙이기] : https://www.acmicpc.net/problem/2667

2. 풀이 전 생각

문제를 다 이해하기까지 오래 걸리진 않았지만 어떻게 풀 것인가에 대한 고민을 많이 했다. dfs와 bfs를 이용해서 푸는건 맞지만 단지를 어떻게 셀지 막막했다.

3. 풀이

import sys

t = int(sys.stdin.readline())
matrix = [list(map(int, sys.stdin.readline().strip()[:t])) for i in range(t)] 
dx = [-1, 1, 0, 0] 
dy = [0, 0, -1, 1] 
cp_num = 0 
house = [] 


def dfs(x, y): 
    global cp_num
    matrix[x][y] = 0 
    cp_num += 1
    for k in range(4): 
        tx = x + dx[k]
        ty = y + dy[k]
        if tx < 0 or tx >= t or ty < 0 or ty >= t: 
            continue
        if matrix[tx][ty] == 1:
            dfs(tx, ty)


for i in range(t):
    for j in range(t):
        if matrix[i][j] == 1: 
            cp_num = 0
            dfs(i, j)
            house.append(cp_num)
house.sort()
print(len(house))
for i in house:
    print(i)

재귀함수를 이용한 dfs로 문제를 풀었고, 집을 발견하면 0으로 바꾼뒤(다른 단지를 찾기위해) 상하좌우 방향으로 집이 있는지 탐색하고 있다면 재귀함수를 통해 반복한다.

4. 풀이하면서 고민했던 점

단지를 어떻게 셀까에 대한 고민을 많이 했던것 같다.

5. 문제를 풀고 난 소감

아직 갈길이 멀다...