[Python/파이썬] 백준 2667 : 단지번호붙이기 (+ 전 코드 리뷰)

이 문제는 보자마자 걍 DFS로 풀어야겠다는 생각을 했습니다.

바로 풀어봅시다.

 

처음에 한 생각은 들어가서 집을 철거해버리고 철거한 만큼의 수를 세어 리스트에 저장하면 되겠다 싶었습니다.

철거해버리면 다음에 그 곳을 셀 필요가 없어지니까요 ㅋㅋ ^_^

위 사진이 정말 적절하다고 생각해서 첨부해봤어요... 철거 해버리면 다시 dfs로 탐색할 때 탐색 못 하니까요.

분명 있었는데... 사라졌으니까 갯수를 셀 수가 없죠...

(visited를 사용하지 않아도 되는 이유가 됩니다)

 

암튼 이 단순한 생각을 그냥 코드로 끄적여봤습니다.

from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

def dfs(x,y):
    global cnt
    # 범위를 벗어났을 때
    if x < 0 or x >= n or y < 0 or y >= n:
        return
    # 집일 때
    if graph[x][y] == 1:
    	# 일단 갯수 세고
        cnt += 1
        # 집 철거
        graph[x][y] = 0
        # 상하좌우 탐색
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx,ny)

graph = []
for _ in range(n):
    graph.append(list(map(int, input().rstrip())))
result = []
cnt = 0

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

# i,j를 이용해 모든 곳을 확인해봅시다.
for i in range(n):
    for j in range(n):
    	# 집 있으면 철거하러 가보자~
        if graph[i][j] == 1:
        	# 철거 시작 ㅋㅋ
            dfs(i,j)
            # 철거 완료
            # 저장합시다.
            result.append(cnt)
            cnt = 0

# sort
ans = sorted(result)
print(len(result))
for i in ans:
    print(i)

전 개인적으로 주석만으로 설명이 될 것 같다고 생각해요... 그냥 하나하나 철거를 해버리는거죠!!

 

그래서 이걸 BFS론 어떻게 하냐면...

 

from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

def bfs(x,y):
    queue = deque()
    queue.append([x,y])
    # 집 철거
    graph[x][y] = 0
    # 이미 우리는 x,y의 위치를 철거 했습니다. 따라서 cnt도 1 추가하고 시작합시다.
    cnt = 1
    while queue:
        x,y = queue.popleft()
        # 집 철거 (처음에 철거한 부분은 신경쓰지 마세요)
        graph[x][y] = 0

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
			
            # 내 관할 아니면 넘어가자
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue

			# 집이 남아있네
            if graph[nx][ny] == 1:
            	# 철거하고
                graph[nx][ny] = 0
                # 이 집과 관련된 것들까지 털어갈테니 명단에 넣어줍시다.
                queue.append([nx,ny])
                # 업적 남기기
                cnt += 1
    return cnt

graph = []
for _ in range(n):
    graph.append(list(map(int, input().rstrip())))
result = []

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

for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            cnt = bfs(i,j)
            result.append(cnt)

ans = sorted(result)
print(len(result))
for i in ans:
    print(i)

---

DFS 전 코드와 비교하며 리뷰하기

이번엔 제가 전에 풀었던 코드와 새로 푼 코드를 비교하며 설명을 적어볼게요.

어차피 제가 보려고 만든 블로그니까요 ㅋㅋ

 

전엔 코드의 상하좌우를 for문으로 하지 않고 하나하나 다 썼었습니다. 그 것 외에도 다른 점이 좀 있는데 뭐가 다른지 함 봐보도록 하겠습니다.

 

우선 그냥 중요한 부분들만 보면서 비교를 해봅시다.

 

기존의 코드

def dfs(x,y):
    if x <= -1 or y <= -1 or x >= n or y >= n:
        return False
    global cnt
    if graph[x][y] == 1:
        cnt += 1
        graph[x][y] = 0
        dfs(x-1,y)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x,y+1)
        return True
    return False
    
## 기타 코드들
    
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            dfs(i,j)
            result.append(cnt)
            cnt = 0

새로운 코드

def dfs(x,y):
    global cnt
    if x < 0 or x >= n or y < 0 or y >= n:
        return
    # 집일 때
    if graph[x][y] == 1:
        cnt += 1
        graph[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx,ny)
            
## 기타 코드들
            
for i in range(n):
    for j in range(n):
        if dfs(i,j) == True:
            result.append(cnt)
            cnt = 0

 

도대체 어떤 점이 다를까요.. (상하좌우 설정 빼고요)

그냥 딱 보면 모르겠습니다. return이 빠져있군요.. 그리고 DFS를 사용하기 위한 for문도 다른 것을 볼 수 있습니다.

 

for문 부터 함 비교를 해봅시다.

 

## 기존의 코드
for i in range(n):
    for j in range(n):
    	# i,j가 return값으로 True를 받았다면
        if dfs(i,j) == True:
            result.append(cnt)
            cnt = 0
            
## 새로운 코드
for i in range(n):
    for j in range(n):
    	# i,j의 위치가 집이라면
        if graph[i][j] == 1:
            dfs(i,j)
            result.append(cnt)
            cnt = 0
            
# 두 코드 모두 i,j로 모든 지도를 탐색할 수 있도록 하였습니다.

조건이 좀 다릅니다. 여기서 확인하기엔 좀 무리가 있는 것 같습니다. 이제 중요한 DFS부분 비교를 해보겠습니다.

## 기존의 코드
def dfs(x,y):
	# 만약 범위를 벗어났다면
    if x <= -1 or y <= -1 or x >= n or y >= n:
    	# False 반환해서 뭐하려고 한거지..
        return False
    global cnt
    # 집일 때
    if graph[x][y] == 1:
    	# 하나 세어주고
        cnt += 1
        # 집 다신 못 세도록 철거
        graph[x][y] = 0
        dfs(x-1,y)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x,y+1)
        return True
    return False

## 새로운 코드
def dfs(x,y):
    global cnt
    # 만약 범위를 벗어났다면
    if x < 0 or x >= n or y < 0 or y >= n:
    	# 돌아가
        return
    # 집일 때
    if graph[x][y] == 1:
    	# 하나 세어주고
        cnt += 1
        # 집 다신 못 세도록 철거
        graph[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx,ny)

기능의 차이는 없지만...

 

기존의 코드는 그냥 DFS함수로 무작정 들어갑니다. 집이 있든 말든 말이죠 ㅋㅋㅋㅋㅋ

그래서 들어간 다음에 집이 없으면 그냥 False를 들고 나와요!

집이 있으면 모든 집을 철거한 뒤에 그 수를 저장하고 True를 반환해줍니다. 일단 집이 있으면 세보겠다 이거죠.

[행동파]

 

새로운 코드는 일단 처음부터 집이 있어야 DFS 함수로 들어갑니다.

들어간 뒤에 다른 곳들을 철거하기 시작하죠.

[효율파]

 

딱히 다른 건 없습니다. 이게 끝이었네요.. 개인적으로 그냥 볼 땐 새로운 코드가 이해하기 쉽네요.

 

근데 백준에 넣어보니 코드는 40ms 로 새로운 코드의 68ms보다 기존 코드가 더 빠릅니다. 기존의 코드도 아래 더보기에 첨부하도록 하겠습니다.

n = int(input())

def dfs(x,y):
    if x <= -1 or y <= -1 or x >= n or y >= n:
        return False
    global cnt
    if graph[x][y] == 1:
        cnt += 1
        graph[x][y] = 0
        dfs(x-1,y)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x,y+1)
        return True
    return False

graph = []
cnt = 0         # 집 개수를 세는 변수
result = []     # 각각의 집 개수를 넣을 리스트

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

for i in range(n):
    for j in range(n):
        if dfs(i,j) == True:
            result.append(cnt)
            cnt = 0

result = sorted(result)
print(len(result))
for i in result:
    print(i)