[소프티어] 장애물 인식 프로그램

https://softeer.ai/practice/6282/history?questionType=ALGORITHM

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

접근

---

• 블록들이 연결되어 있는 경우, 같은 구역으로 인식
  → DFS로 좌우상하 점검
• 새로운 구역 찾기
  → 반복문을 사용해 아직 방문하지 않은 블럭 모두 점검

 

코드

---

주의점

• 2차원 배열 선언 및 초기화 시 주의점

visit = [[False] * n] * n #visit[0][0] 값 변경할 경우, 참조 타입으로 인해 모든 행의 0번째 열 값이 변경된다.

visit = [[False] * n for _ in range(n)] # 이렇게 선언하기

import sys

n = int(input())
data = [list(map(int,sys.stdin.readline().rstrip())) for _ in range(n)]
visit = [[False] * n for _ in range(n)]
count = 0

def search(i, j):

    global count
    
    for coord in [[0,1],[1,0],[0,-1],[-1,0]]:
        
        row, col = i+coord[0], j+coord[1]
        
        if 0<=row<n and 0<=col<n and data[row][col] == 1 and visit[row][col] == False:
            visit[row][col] = True
            count += 1
            search(row,col)

answer = []
for i in range(n):
    for j in range(n):
        if data[i][j] == 1 and visit[i][j] == False:
            count = 1
            visit[i][j] = True
            search(i, j)
            answer.append(count)

print(len(answer))
for i in sorted(answer):
    print(i)