[Softeer / Level2] 장애물 인식 프로그램

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

Softeer

---

 

문제를 보자마자 백준문제(2667번 / 단지번호 붙이기) 에서 풀었던 문제가 떠올랐다.

동일한 문제여서 쉽게 해결할 수 있었다.

 

복기해야하는 점은

1. 격자 벗어나는 부분(종료조건) 또는 0이면 False 리턴
2. 방문을 했으면 방문표시 (1 -> 0)으로 표시하여 탐색한곳 다시 탐색하지 않도록 방지
3. 문제 조건에 맞게 정렬을 한다.

<내 코드>

import sys

def dfs(S, x, y):
    global cnt
    if x <= -1 or x >= N or y <= -1 or y >= N:
        return False
    if S[x][y] == '1':
        cnt += 1
        S[x][y] = '0'
        dfs(S, x-1, y)
        dfs(S, x, y-1)
        dfs(S, x+1, y)
        dfs(S, x, y+1)
        return True
    return False

S, visited = [], []
N = int(sys.stdin.readline())
for _ in range(N):
    S.append(list(input()))

global cnt
result = 0          # total block
for i in range(N):
    for j in range(N):
        cnt = 0
        if dfs(S, i, j) == True:
            visited.append(cnt)
            result += 1

visited.sort()
print(result)
for q in visited:
    print(q)