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

생성일: 2022년 2월 17일 오후 3:47

구현 코드

# 단지 번호 붙이기 (DFS, BFS)
import sys
from collections import deque
sys.stdin = open("input.txt", "rt")

def BFS(blankX, blankY):
    Q = deque()
    Q.append((blankX, blankY))
    isOne = False
    while Q:
        tmp = Q.popleft()
        for j in range(5):
            x = tmp[0]+dx[j] # x좌표
            y = tmp[1]+dy[j] # y좌표
            if 0<=x<n and 0<=y<n:
                if board[x][y] == 1 and ch[x][y] == 0:
                    isOne = True
                    ch[x][y] = 1
                    res[x][y] = L
                    cnt[L-1] += 1
                    Q.append((x,y))
                if board[x][y] == 0 and ch[x][y] == 0:
                    ch[x][y] = 1
                    res[x][y] = 0

    return isOne

if __name__ == "__main__":
    n = int(input())
    board = []
    for _ in range(n):
        board.append(list(map(int, input())))
    res = [[-1 for _ in range(n)] for _ in range(n)]

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

    ch = [[0 for _ in range(n)] for _ in range(n)]

    L = 1
    isdone = False
    cnt = []

    for i in range(n):
        for j in range(n):
            if board[i][j] == 0:
                res[i][j] = 0
            else:
                if res[i][j] == -1:
                    cnt.append(0)
                    isOne = BFS(i,j)
                    if isOne:
                        L += 1

    print(L-1)
    cnt.sort()
    for x in cnt:
        print(x)

모범 답안 (DFS)

import sys
sys.stdin=open("input.txt", "r")
dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]

def DFS(x, y):
    global cnt
    cnt+=1
    board[x][y]=0 #이렇게 처리하였기 때문에 한번 방문한 곳은 재방문 x
    for i in range(4):
        xx=x+dx[i]
        yy=y+dy[i]
        if 0<=xx<n and 0<=yy<n and board[xx][yy]==1:
            DFS(xx, yy)

if __name__=="__main__":
    n=int(input())
    board=[list(map(int, input())) for _ in range(n)]
    res=[]
    for i in range(n):
        for j in range(n):
            if board[i][j]==1:
                cnt=0
                DFS(i, j)
                res.append(cnt)
    print(len(res))
    res.sort()
    for x in res:
        print(x)

모범 답안 (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)

차이점

• 내가 구현한 코드에서는 BFS사용
• 모범 답안 (DFS)기준
  • 나는 L과 cnt 를 통해 총 단지 수와 각 단지별 집의 수를 따로 구하였다.
  • 모범 답안에서는 res 배열에 집의 수를 저장하였고, 이는 곧 len(res)는 단지 수를 의미한다.
  • 나는 한번 방문한 곳을 체크하기 위해 ch 배열을 따로 만들어서 체크 리스트로서 관리했지만, 모범 답안에서는 곧바로 board 리스트의 값을 0으로 처리하여 트래킹하였다. (추가적인 변수 생성 x ⇒ 메모리 효율 up)
  • 입력받은 board 리스트의 값을 변경하지 않고 보존하려 했기 때문에 로직도 복잡해지고 코드의 효율성도 저하되었다. ⇒ 정답을 구하는데 지장이 없다면 입력 데이터를 변형하여도 무관하다.