파이썬 알고리즘 066 | 단지 번호 붙이기(DFS, *BFS*) *****

66. 단지 번호 붙이기(DFS, BFS)

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

▣ 입력설명
첫 번째줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력
되고 그 다음 N줄에는 각각 N개의 자료(0 혹은 1)가 입력된다
▣ 출력설명
첫 번째줄에는 총 단지수를 출력하시오. 그리고 각 단지내의 집의 수를 오름차순으로 정렬하
여 한줄에 하나씩 출력하시오
▣ 입력예제 1
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
▣ 출력예제 1
3
7
8
9

<내 풀이>

일단 상하좌우로 돌면서 체크를 하다가
주변에 아무데도 갈데가 없으면 다른 모서리로 이동해주려고 했는데
다른 모서리까지 한 단지일 수도 있는거고 (0,n)-(n,0)-(n,n)을 한번씩 돌아볼 방법도 구현을 못하겠음

(1)- 풀이를 듣고 구현해보는데 막히는 부분이 존재함
=> dfs를 끝내고 다시 이중for문으로 돌아가는 방법

• #=>는 풀이 듣고 잘못된 점 파악해서 풀이법 써준 것

dx=[-1,0,1,0]
dy=[0,1,0,-1]
def dfs(x,y):
    global cnt
    if #이 부분을 어떻게 설정해줘야 dfs를 끝낼 수 있는지 모르겠음
        res.append(cnt) #=>이 부분을 굳이 if 에 안넣어도 되고 밑에 dfs호출하고 난 뒤에 넣어주면 된다, dfs다 겪은 후에 
    else :
        for i in range(4) :
            xx=x+dx[i]
            yy=y+dy[i]
            if 0<=xx<=n-1 and 0<=yy<=n-1 and a[xx][yy]==1:
                a[xx][yy]=0
                cnt+=1
                dfs(xx,yy)
    

if __name__=='__main__' :
    cnt=0 #=> cnt를 여기다가 두면 초기화가 되지 않고 계속해서 누적이 되고 만다
    res=[]
    n=int(input())
    a=[list(map(int, input())) for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if a[i][j]==1:
                a[i][j]=0
                dfs(i,j)
res.sort()
print(len(res))
for i in res:
    print(i)
                

(2) 위의 풀이를 수정한 것
==>근데 여기서도 잘못된 부분 있었음 dfs를 호출하기 전에 cnt불러주는데
dfs 안에서 최초의 값은 cnt에 추가를 안해주기 때문에 처음에 cnt=1이라고 초기화를 해주어야 한다

dx=[-1,0,1,0]
dy=[0,1,0,-1]
def dfs(x,y):
    global cnt
    for i in range(4) :
            xx=x+dx[i]
            yy=y+dy[i]
            if 0<=xx<=n-1 and 0<=yy<=n-1 and a[xx][yy]==1:
                a[xx][yy]=0
                cnt+=1
                dfs(xx,yy)
    
if __name__=='__main__' :
    res=[]
    n=int(input())
    a=[list(map(int, input())) for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if a[i][j]==1:
                cnt=0
                a[i][j]=0
                dfs(i,j)
                res.append(cnt)
res.sort()
print(len(res))
for i in res:
    print(i)
    

(3) 최종 수정 풀이

dx=[-1,0,1,0]
dy=[0,1,0,-1]
def dfs(x,y):
    global cnt
    for i in range(4) :
            xx=x+dx[i]
            yy=y+dy[i]
            if 0<=xx<=n-1 and 0<=yy<=n-1 and a[xx][yy]==1:
                a[xx][yy]=0
                cnt+=1
                dfs(xx,yy)
    
if __name__=='__main__' :
    res=[]
    n=int(input())
    a=[list(map(int, input())) for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if a[i][j]==1:
                cnt=1 #=> cnt를 1로 설정했어야 한다. 선생님은 dfs 호출한 이후에 1을 꼬박꼬박 더해줬기에 여기를 0으로 했지만 나는 처음거는 안세주기 때문에 여기서 하나 세주어야 한다
                a[i][j]=0
                dfs(i,j)
                res.append(cnt)
res.sort()
print(len(res))
for i in res:
    print(i)

<풀이>

(1) 우선 이중 for문으로 돌며 한 행씩 체크해주다가 1이 발견되는 데부터
dfs 호출해주고 상하좌우 탐색을 해준다,
그리고 이 1부분을 0으로 바꿔주고
cnt+=1(단지 갯수를 세야하니깐)
(2) 그리고 다 막혀버리면 dfs 하나 끝나는 것 - 센 단지 숫자를 리스트에 추가
(3) dfs 하나 끝나면 아까 이중 for문 돌던 부분으로 돌아감
(4) 또 탐색하다가 1이 나온 부분 찾으면 탐색해주고 0으로 바꿔주고 카운팅 해주기
[1] DFS

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

def dfs(x, y):
    global cnt
    cnt+=1 #하나가 넘어오면 카운트 시작 일단
    a[x][y]=0
    for i in range(4) :
        xx=x+dx[i]
        yy=y+dy[i]
        if 0<=xx<=n-1 and 0<=yy<=n-1 and a[xx][yy]==1:
            dfs(xx,yy)
   

if __name__=="__main__":
    res=[]
    n=int(input())
    a=[list(map(int, input())) for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if a[i][j]==1:
                cnt=0 #여기서 초기화를 해줬어야 한다! 단지마다 세는 것이니깐
                dfs(i,j)
                res.append(cnt) #res에 cnt더해주는 것 여기서 하기

res.sort()
print(len(res))
for i in res:
    print(i)

[2] BFS

import sys
from collections import deque
sys.stdin=open("input.txt", "r")
dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
n=int(input())
board=[list(map(int, input())) for _ in range(n)]
cnt=0
res=[]
Q=deque()
for i in range(n):
    for j in range(n):
        if board[i][j]==1:
            board[i][j]=0
            Q.append((i, j))
            cnt=1
            while Q:
                tmp=Q.popleft()
                for k in range(4):
                    x=tmp[0]+dx[k]
                    y=tmp[1]+dy[k]
                    if x<0 or x>=n or y<0 or y>=n or board[x][y]==0:
                        continue
                    board[x][y]=0
                    Q.append((x, y))
                    cnt+=1
            res.append(cnt)

print(len(res))
res.sort()
for x in res:
    print(x)
    

<반성점>

• 풀이 방법을 듣고 구현해보는데 def dfs부분에서 if 쪽을 어떻게 설정해야할 지 감이 잡히지 않았음
• 굳이 dfs에서 if 꼭 넣지 않아도 된다. dfs는 단순 반복문일뿐.. 이런 유형도 있단 점을 꼭 명심하자

<배운 점>

• cnt 초기화 부분 <=dfs부르기 직전에
• res.append() 부분 <= dfs다 돌리고 온다
• 이중 for문을 돌리다가 1이었던 부분을 찾게 되면
  그때서야 dfs를 호출하고, 상하좌우 돌면서 1아이들을 찾으면
  1인 아이들을 0으로 바꿔주다가 다 찾으면 다시 for문으로 돌아가고,
  나중에 다른 단지 애들이 만나도 0이니깐 얘네 포함하지 않게 해주는 방법 기억하기

<2회독 내 풀이>

def dfs(x,y) :
    global cnt
    for i in range(4) :
        cnt+=1 #이걸 여기다가 두어서 오류, 이 for문 돌리기전에 넣어줘야지
        a[x][y]=0 #이것두
        xx=dx[i]+x
        yy=dy[i]+y
        if 0<=xx<n and 0<=yy<n and a[xx][yy]==1:
            dfs(xx,yy)
if __name__=='__main__' :
    res=[]
    cnt=0
    dx=[-1,0,1,0]
    dy=[0,-1,0,1]
    n=int(input())
    a=[list(map(int,input())) for _ in range(n)]
    for i in range(n) :
        for j in range(n):
            if a[i][j]==1:
                cnt=0
                dfs(i,j)
                res.append(cnt)
print(res)

=> 수정한 내 풀이

def dfs(x,y) :
    global cnt
    cnt+=1
    a[x][y]=0
    for i in range(4) :
        
        xx=dx[i]+x
        yy=dy[i]+y
        if 0<=xx<n and 0<=yy<n and a[xx][yy]==1:
            dfs(xx,yy)
if __name__=='__main__' :
    res=[]
    cnt=0
    dx=[-1,0,1,0]
    dy=[0,-1,0,1]
    n=int(input())
    a=[list(map(int,input())) for _ in range(n)]
    for i in range(n) :
        for j in range(n):
            if a[i][j]==1:
                cnt=0
                dfs(i,j)
                res.append(cnt)
print(len(res))
for i in res:
    print(i)