[python] 2667번 - 단지번호붙이기

문제

파이썬 풀이

2차원 리스트에서의 탐색은 어떤 식으로 해야 하는지 이해하는데 조금 어려웠었다.

여기서의 포인트는 탐색할 방향인 상하좌우를 이동 좌표를 리스트에 담아 for문을 통해 탐색을 진행하는 것이다.

그리고 탐색의 방법도 dfs를 통해 재귀로 탐색하였다.

 

좌표 리스트

dx=[-1,0,1,0]
dy=[0,1,0,-1]

해당 좌표는 dx, dy에서 같은 인덱스끼리 묶어보면 (-1, 0), (0, 1), (1, 0), (0, -1)로 각각 좌(x축으로 -1 이동), 상(y축으로 +1 이동), 우(x축으로 +1 이동), 하(y축으로 -1 이동)를 의미한다.

DFS 탐색 함수

def dfs(x,y) :
    global cnt
    matrix[x][y] = "0" #방문한 곳 0으로 만들기
    cnt+=1 #카운트 수 늘리기
    for i in range(4) : #상하좌우로 움직이기
        nx = x +dx[i]
        ny = y +dy[i]
        if nx < 0 or nx >= n or ny < 0 or ny >= n :
            #만약 움직인 좌표가 범위를 벗어났다면 continue
            continue
        if matrix[nx][ny] == "1" :
            #움직인 좌표에 집이 있다면 다시 dfs탐색
            dfs(nx,ny)

방문한 곳은 0으로 만들어 다시 방문하지 못하도록 만든다

단지에 모여있는 집의 수를 세기 위해 방문할 때 마다 카운트 수를 늘려준다.

for문을 통해 i 를 0~3까지 돌리면서 이동 좌표 dx [i], dy [i]를 통해 상, 하, 좌, 우로 이동해준다.  

그리고 혹시나 이동한 좌표가 범위를 벗어나는 값이면 continue를 이동하지 않도록 한다.

그리고 이동한 곳의 값이 1이면 집이 있으므로 dfs에 새로 이동한 값인 nx,ny를 넣어 재귀를 통해 다시 탐색한다.

 

시작 지점 찾기

for i in range(n) :
    for j in range(n) :
        #이중 for문으로 matrix를 하나하나 돌으면서 1인 구간 찾기(시작점 찾기)
        if matrix[i][j]=="1" :
            cnt = 0 #시작 전 카운트 초기화
            dfs(i,j)
            result.append(cnt) #탐색 끝난 후 카운트 값 저장

이중 for문을 통해 2차원 리스트의 모든 인덱스에 접근하면서 1인 구간을 찾는다.

1인 구간을 찾으면 탐색을 시작한다. 탐색이 끝나면 한 단지의 탐색이 끝난 것이므로, result의 해당 단지의 주택 수를 저장한다.

다시 반복 for문을 돌며 다른 단지의 시작점을 찾게 된다.

 

전체 코드

import sys
input = sys.stdin.readline

dx=[-1,0,1,0]
dy=[0,1,0,-1]
n=int(input().rstrip())
matrix=[list(input().rstrip()) for _ in range(n)]

cnt = 0
result=[]

def dfs(x,y) :
    global cnt
    matrix[x][y] = "0" #방문한 곳 0으로 만들기
    cnt+=1 #카운트 수 늘리기
    for i in range(4) : #상하좌우로 움직이기
        nx = x +dx[i]
        ny = y +dy[i]
        if nx < 0 or nx >= n or ny < 0 or ny >= n :
            #만약 움직인 좌표가 범위를 벗어났다면 continue
            continue
        if matrix[nx][ny] == "1" :
            #움직인 좌표에 집이 있다면 다시 dfs탐색
            dfs(nx,ny)

for i in range(n) :
    for j in range(n) :
        #이중 for문으로 matrix를 하나하나 돌으면서 1인 구간 찾기(시작점 찾기)
        if matrix[i][j]=="1" :
            cnt = 0 #시작 전 카운트 초기화
            dfs(i,j)
            result.append(cnt) #탐색 끝난 후 카운트 값 저장

print(len(result))
result.sort()
for c in result :
    print(c)