[백준] 2667번 단지번호붙이기

사용 언어 - Python3

2667번: 단지번호붙이기 (실버1, DFS 문제)

문제 ★코테 자주 등장하는 DFS 문제★

2667번: 단지번호붙이기

 

정답

DFS 재귀함수 

(정답 풀이)

1. dfs 함수 정의

1.1. 1 값인 x,y 좌표 찾기

x,y가 N*N 정사각형 범위 안에 없다면 return해준다.

N*N 정사각형 범위 안에 속해있다면, 1이 있는 좌표 x,y를 찾는다.

• 개수를 한개씩 더해주면서 1이 있는 총 개수를 카운트한다. (count+=1)
• 방문한 좌표는 0으로 만들어 방문했다는 표시를 해준다. (graph[x][y]=0)

1.2. x,y 좌표 업데이트

x,y를 상하좌우 range(4) 만큼 업데이트하면서 이동한 위치를 반영한 nx, ny로 업데이트해준다.

1.3. dfs(nx,ny)

새로운 좌표 nx,ny로 dfs 재귀함수를 돌린다.

상하좌우에 1이 없을 때까지 1.1~1.2를 계속 반복한다.

2. graph 탐색 for문

좌표값이 1인 graph를 찾아서 총 카운트 값을 result 리스트에 append한다.

result에 저장했기 때문에 count는 다시 0으로 지정하여 리셋해주고, 다시 탐색을 시작한다.

3. 출력

result의 개수 = 총 단지수

"result = 각 단지 내 집의 수" 를 오름차순으로 정렬하여 프린트한다.

# 정답
import sys
#from collections import deque

input = sys.stdin.readline()
N = int(input())

graph = []
result = []
count = 0

for _ in range(N):
    graph.append(list(map(int,input().rstrip())))

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

def dfs(x,y):
    global count
    
    if x<0 or x>=N or y<0 or y>=N:
    	return
    
    if graph[x][y] == 1:
    	count += 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 graph[i][j] == 1:
            dfs(i,j)
            result.append(count)
            count = 0
            
result.sort()
print(len(result))
for cnt in result:
	print(cnt)

 

공부한 내용

• 파이썬 global 사용법

함수 밖에서도 count (지역)변수를 호출하고 사용하기 위해선 지역변수를 전역변수로 선언해야한다.

함수 안, 밖에서 gloabl count(변수명)을 하면 전역변수로 선언된다.

 

• strip()

strip() : 인자를 지정하지 않으면, 문자열에서 공백을 제거한다.

strip('a') : 문자열의 왼쪽과 오른쪽에서 'a'를 제거한다.

lstrip('a') : 문자열의 왼쪽에서 'a'를 제거한다.

rstrip('a') : 문자열의 오른쪽에서 'a'를 제거한다.

 

 

 

---

레퍼런스

• 정답 참고 (설명이 잘되어있습니다)

백준 2667번 파이썬 문제풀이(큐와 그래프 - 단지번호붙이기) - DFS, BFS

• 파이썬 global 전역변수 사용법

파이썬 global 전역변수 사용방법과 사용예 알아보기!

• rstrip 오른쪽부터 문자제거

Python - String strip(), rstrip(), lstrip() 사용 방법 및 예제

• 깃허브 정답

GitHub - yyeongeun/codingtest: 코딩테스트 공부