[Python] 2667번 : 단지번호붙이기

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

2667번: 단지번호붙이기

 

문제 3줄 요약

1. 정사각형 모양의 지도가 있다.

2. 집이 있는 곳은 1, 없는 곳은 0을 표시한다.

3. 집의 모임을 단지라고 정의하는데, 단지수를 출력하고 속하는 집의 수를 오름차수으로 정렬하라!

 

---

 

예시를 보면 이해하기 수월하다.

 

1의 모임을 단지라고 부르고,

단지수를 먼저 출력한다. 위의 <그림 2>에서는 3 단지가 있는 것을 볼 수 있다.

 

다음은 단지에 속하는 집의 수를 출력하는데,

단지 1은 7 가구, 단지 2는 8 가구, 단지 3은 9 가구가 있다.

따라서

출력은 3 7 8 9가 되겠다.

 

코드로 작성해보자!

 

---

 

탐색 문제이므로

DFS와 BFS를 사용하면 되겠다.

 

위의 문제 경우에는 두 가지 중

어떤 것을 선택해도 풀 수 있다.

 

오늘 글에서는

DFS로 풀어보도록 하겠다.

 

---

STEP 1)

지도의 정보를 담을 리스트와

탐색에 필요한 방문 유무를 체크해줄 리스트를 선언해준다.

 

그 후 반복문을 돌다가

방문하지 않은 집(1)을 발견한다면,

해당 좌표로부터 DFS를 통해 근처 집을 모두 탐색한다.

 

from sys import stdin

# N * N 지도
N = int(stdin.readline())

# v_list : 지도 정보
# visited : 좌표 방문 유무
# answer_list : 단지내 가구수
v_list, visited, answer_list = [], [[1]*(N) for _ in range(N)], []

# 지도 정보 업데이트
for _ in range(N):
    v_list.append(list(map(int,stdin.readline().rstrip())))

# 집을 발견한다면, 근처 가구수를 파악한다.
for x in range(N):
    for y in range(N):
        if (v_list[x][y] == 1) and (visited[x][y]):
            answer_list.append(dfs(x,y))

print(len(answer_list))
for ans in sorted(answer_list):
    print(ans)

---

STEP 2)

DFS를 통한 탐색

 

특히 지도라는 문제 특성상

해당 좌표에서 상하좌우를 파악해야하는데,

이런 탐색을

델타 탐색이라고 부른다.

 

델타 탐색은

2차 배열의 한 좌표에서 4방향(혹은 8방향 등 필요 요소)의 인접 배열 요소를 탐색하는 방법

라고 정의된다.

 

따라서 이번 DFS에서도

델타 탐색을 이용한다.

 

dx, dy 리스트를

반복문을 통해 x 방향에 -1, 1,

y 방향에 -1, 1를 차례대로 연산해줌으로써

4방향을 탐색한다.

 

def dfs(x,y):
    dfs_list, cnt = [(x,y)], 0
    
    # 델타 탐색
    dx = [0,0,-1,1]
    dy = [-1,1,0,0]
    
    while(len(dfs_list) > 0):
        x, y = dfs_list.pop()
        if visited[x][y]:
            visited[x][y] = 0
            cnt += 1
            
            # 상하좌우 탐색
            for move in range(4):
                next_x = x + dx[move]
                next_y = y + dy[move]

                if (next_x >= 0) and (next_x < N) and (next_y >= 0) and (next_y < N):
                    if (visited[next_x][next_y]) and (v_list[next_x][next_y]):
                        dfs_list.append((next_x, next_y))

    return cnt

탐색 후

방문한 적이 없으며, 집(1)의 위치인 경우

DFS 스택에 삽입하여 다음 탐색을 이어간다.

 

위치를 찾는 경우에만

cnt 를 1씩 증가시킨 후,

탐색 종료시 cnt를 반환해주고 다시 반복문을 통해 방문하지 않은 집(1)의 좌표를 찾는다.

 

---

 

최종 코드

 

from sys import stdin

def dfs(x,y):
    dfs_list, cnt = [(x,y)], 0
    dx = [0,0,-1,1]
    dy = [-1,1,0,0]
    
    while(len(dfs_list) > 0):
        x, y = dfs_list.pop()
        if visited[x][y]:
            visited[x][y] = 0
            cnt += 1
            for move in range(4):
                next_x = x + dx[move]
                next_y = y + dy[move]

                if (next_x >= 0) and (next_x < N) and (next_y >= 0) and (next_y < N):
                    if (visited[next_x][next_y]) and (v_list[next_x][next_y]):
                        dfs_list.append((next_x, next_y))

    return cnt

N = int(stdin.readline())
v_list, visited, answer_list = [], [[1]*(N) for _ in range(N)], []

for _ in range(N):
    v_list.append(list(map(int,stdin.readline().rstrip())))

for x in range(N):
    for y in range(N):
        if (v_list[x][y] == 1) and (visited[x][y]):
            answer_list.append(dfs(x,y))

print(len(answer_list))
for ans in sorted(answer_list):
    print(ans)

 

델타 탐색은 정말 유용하게 사용되니

익숙해질 때까지 사용해보자!

 

끝.