🎀 본 게시물은 Softeer 연습문제 풀이 게시물입니다. 🎀

---

https://softeer.ai/practice/info.do?idx=1&eid=409&sw_prbl_sbms_sn=174849

입력예제1

7
1110111
0110101
0110101
0000100
0110000
0111110
0110000

출력예제1

3
7
8
9

대표적인 DFS 문제이다. 장애물, 아파트단지 등등

---

🚀 나의 풀이 ⭕

import sys

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

def DFS(x,y):
    global cnt
    cnt+=1
    board[x][y]=0                                       # 내가 밟은 곳은 다시 확인 안할 거니 0으로 만들고
    for i in range(4):                                  # 상하좌우 4방향을을 살핀다
        xx=x+dx[i]
        yy=y+dy[i]
        if 0<=xx<n and 0<=yy<n and board[xx][yy]==1:    # 격자판 안에서 4방향중 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:      # 1이 발견되면 장애물
                cnt=0
                DFS(i,j)            # 발견된 장애물을 기준으로 주변을 살펴보자
                res.append(cnt)     # 업데이트 된 단지의 건물수를 넣어준다
    print(len(res))                 # 단지수 출력
    res.sort()
    for x in res:
        print(x)                    # 단지의 건물수 출력

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기