[2667번] 단지번호 붙이기 / python3 (DFS의 향연, 추후 BFS 업로드예정)

[10989번] 수 정렬하기 3 / python3  (feat. sys.stadin.readline( ))

 

문제 링크: https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

---

❌ 1~3차시도 실패

기존에 숫자 연결문제에서처럼 visit 리스트를 만들어 방문을 체크해보려했는데....

너무 헷갈리거니와... 구하는 것도 여러 개이기에 방법 포기데쓰

 

역시나 다른 분들이 풀이한 것을 참고하여 비교해가며 어떻게 풀이했나살펴보았다.

그런 과정 중 상하좌우 살피는 과정 중, 기존 배웠던 방법과 새로운 방법들이 보임

---

❓ 정답은 ??

기존 방법

#n*n 맵크기
#첫째줄 총 단지 수
#둘째줄~ 각 단지마다 집의 개수
 
n=int(input()) #지도의 크기
graph=[]
#맵 데이터 받기
for _ in range(n):
    graph.append(list(map(int,input())))
 
result = [] #아파트 로드맵
cnt = 0  #아파트안 집 갯수 세기
 
def dfs(x,y):
    global cnt
    if x<=-1 or y<=-1 or x>=n or y>=n:
        return
    if graph[x][y]==1:
        graph[x][y]=0
        cnt+=1
        dfs(x-1,y)  #왼쪽
        dfs(x+1,y)  #오른쪽  
        dfs(x,y-1)  #아래
        dfs(x,y+1)  #위
        return
 
 
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            cnt = 0
            dfs(i,j)
            result.append(cnt)
 
print(len(result)) #아파트 몇 동?
result.sort()
for i in result: #각 리스트의 cnt 꺼내고
    print(i)

새로운 방법

n = int(input())    #지도 가로,세로
 
 
graph = []  #맵 데이터 넣기
for _ in range(n):
    graph.append(list(map(int,input())))
 
result = [] #아파트 로드맵
cnt = 0  #아파트안 집 갯수 세기
 
dx = [0,0,1,-1] #상하좌우 인접한 곳의 좌표를 구하기 위함 
dy = [1,-1,0,0]
 
 
def dfs(x,y):
    global cnt
    graph[x][y] = 0   #방문한 곳을 따로 체크하는 visit 리스트를 만들기보다 0으로 만들어서 체크를 하는 게 이득
    cnt += 1 #탐색을 시작할 때마다 카운트를 더해준다 
    for k in range(4): #상하좌우 인접한 네 방향에 대해서 
        nx = x + dx[k]
        ny = y + dy[k]
        if nx<=-1 or ny<=-1 or nx>=n or ny>=n: #맵 안에서 찾을 수 있게 제한
            continue    
        if graph[nx][ny] ==1: #인접한 곳의 좌표가 범위 내이고, 1이라면 
            dfs(nx,ny) #조건을 만족하는 지점에서 다시 탐색을 시작한다 
 
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            cnt = 0
            dfs(i,j)
            result.append(cnt)
 
 
print(len(result)) # 아파트 동 갯수 구하기
# result= [7,8,9] 우연히 오름차순으로 리스트에 들어감
 
result.sort()   #오름차수 정렬
for i in result:    #각 리스트의 cnt 꺼내고
    print(i)

---

💯 풀이 과정

* 일단 포인트는 방문한 리스트를 따로 만들 필요없이 0으로 처리하여 다시 방문안하도록

* 아파트 몇 동까지 있는 지 구할 때 따로 카운트 변수를 넣기보다는 리스트 개수 len( ) 활용

---

😎오늘의 한줄평: DFS,BFS 한꺼번에 하려고해서 헷갈리는 거 아닐까? DFS 부터 정복 후 BFS방법으로 다시 한번 풀자