백준 2667번 단지번호붙이기 파이썬 풀이

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

---

정답 코드1

n = int(input())
graph = []
num = []

for i in range(n):
    graph.append(list(map(int, input())))

#상하좌우
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def DFS(x, y):
    if x < 0 or x >= n or y < 0 or y >= n:
        return False

    if graph[x][y] == 1:
        global count
        count += 1
        graph[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            DFS(nx, ny)
        return True
    
count = 0
result = 0

for i in range(n):
    for j in range(n):
        if DFS(i, j) == True:
            num.append(count)
            result += 1
            count = 0

num.sort()
print(result)
for i in range(len(num)):
    print(num[i])

 

Q)dfs(0,1) ->  dfs(1,1)  이런 식으로 depth가 증가하면서 재귀함수가 돌면 dfs(1,1) 같은 경우도 return True 하게 되는 거 아닌가요??

-> graph[x][y] = 0 에 의해 1이 0으로 바뀌므로 아래의 for 문이 돌 때는 if graph[x][y] == 1 이 아니므로 return True가 되는 상태가 아니게 됩니다.

for i in range(n):
    for j in range(n):
        if DFS(i, j) == True:
            num.append(count)
            result += 1
            count = 0

위의 코드에서 재귀함수의 순서는 아래와 같다

이중 DFS(0,1) -> DFS(0,2) ->DFS(0,3)을 그래프 상으로 표시해보면 아래와 같다.

 

정답코드2

from sys import stdin
n = int(input())
# 데이터 저장용 공간 matrix
matrix = [[0]*n for _ in range(n)]
# 방문 내역 저장용 visited
visited = [[0]*n for _ in range(n)]

# matrix에 아파트 유무 0과 1 저장
for i in range(n):
    line = stdin.readline().strip()
    for j, b in enumerate(line):
        matrix[i][j] = int(b)

# 방향 확인용 좌표 dx와 dy
# 중앙을 기준으로 좌/우/위/아래
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

# DFS 함수 정의
def dfs(x, y, c):
    visited[x][y] = 1   # 방문 여부 표시
    global nums            # 아파트 단지 수를 세기위한 변수
    # 아파트가 있으면 숫자를 세어줍니다.
    if matrix[x][y] == 1:
        #matrix[x][y] = c # 아파트 단지별 숫자 표시용
        nums += 1
    # 해당 위치에서 좌/우/위/아래 방향의 좌표를 확인해서 dfs 적용
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n:
            if visited[nx][ny] == 0 and matrix[nx][ny] == 1:
                dfs(nx,ny, c)

cnt = 1 # 아파트 단지 세기 위한
numlist = [] # 아파트 단지별 숫자
nums=0 # 아파트 수
for a in range(n):
    for b in range(n):
        if matrix[a][b] == 1 and visited[a][b] == 0:
            dfs(a,b,cnt)
            numlist.append(nums)
            nums = 0
#            cnt += 1 # 아파트 단지 별 표시용

print(len(numlist))
for n in sorted(numlist):
    print(n)

 

개인적으로 풀이2가 더 직관적이라 좋은 것같다.

 

배운점 && 공부 방향

 

1. 상하좌우를 체크하는 방법으로 아래와 같은 방법이 존재한다.

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
	for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

 

2. 재귀함수가 도는 구조가 너무 헷갈린다.

 -> 다양한 문제를 많이 풀어보는 수밖에 없다. 노트에 과정을 정리해보는 연습을 하자.

 

 

3.DFS 구조는 결국 갔다온 것을 check하는 것 + promising 조건을 설계하는 것 이 두가지가 핵심이다.

 

4. 기존 코드에서의 문제점 분석하기

기존코드

import sys

n = int(input())

#그래프 생성하기
graph = []
for i in range(n):
    graph.append(list(map(int,sys.stdin.readline().rstrip())))

#들어왔는지 체크
visited = [[0] *(n) for _ in range(n)]

for i in visited:
    print(i)

print("\n")
#단지 배열
num = []
count = 0
#상하좌우
dx = [0,0,-1,1]
dy = [-1,1,0,0]

def DFS(x,y):
    global count
    

    if(visited[x][y] == 0 and graph[x][y] == 1):
        count += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            #방문 체크
            #범위 설정
            if(nx >= 0 and nx < n and ny >= 0  and ny < n):
                visited[nx][ny] = 1
                DFS(nx,ny)


for i in range(n):
    for j in range(n):
        if(visited[i][j] == 0 and graph[i][j] == 1):
            DFS(i,j)
            num.append(count)
            count = 0
for i in visited:
    print(i)

num.sort()

print(len(num))

for i in num:
    print(i)

출력값

 

문제점

 -DFS 함수 정의 부분이 틀렸음.

 

1. DFS(x,y) 함수 호출 시 바로 탐색이 된 상태인 것을 코드로 짜는 것이므로, if 문보다 더 앞서 visited[x][y] = 1 을 해주어야했음.

2. 마찬가지로 count += 1 을 if 문 보다 앞서 했어야 함.

 

3. 왜 이런 결과가 도출 되었을까?

 

 -> 이렇게 코드를 짜면 visited 가 1이 된 채로 시작하므로 다음 depth에선 visited == 0 의 조건을 무조건 충족하지 못해 count 1 해서  코드가 끝나고 다음으로 넘어가게 된다. 따라서 모두 1만 도출 된 것이다.

if(visited[x][y] == 0 and graph[x][y] == 1):
        count += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            #방문 체크
            #범위 설정
            if(nx >= 0 and nx < n and ny >= 0  and ny < n):
                visited[nx][ny] = 1
                DFS(nx,ny)

따라서 아래와 같이 코드를 수정해줘야한다.

global count
    count += 1
    visited[x][y] = 1
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]  

        if(0 <= nx < n and 0 <= ny < n):
            if(visited[nx][ny] == 0 and graph[nx][ny] == 1):
                DFS(nx,ny)

->DFS를 설계할 땐 promising 한 다음 단계를 고려하면서 설계해야한다.