[Softeer] 장애물 인식 프로그램 Lv.2 (파이썬 python)

 

문제 링크

 

https://softeer.ai/practice/6282

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

 

 

문제 풀이

 

def dfs(x, y):
    if x < 0 or x >= n or y < 0 or y >= n:
        return False
    if graph[x][y] == 1 and not visited[x][y]:
        global count
        visited[x][y] = 1
        count += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)
        return True
    return False

n = int(input())
graph = [list(map(int, input())) for _ in range(n)]
visited = [[0] * n for _ in range(n)]
count = 0
block = 0
obstacle = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
for i in range(n):
    for j in range(n):
        if dfs(i, j):
            obstacle.append(count)
            block += 1
            count = 0
obstacle.sort()
print(block)
for o in obstacle:
    print(o)

 

 

DFS - 재귀로 해결 가능한 문제입니다.

입력받은 그래프에 대해 DFS를 돌려, 이어진 장애물들을 탐색합니다.

처음 기준이 되는 장애물 위치에서 4방향으로 계속해서 뻗어나가며 이어진 장애물들에 대해 모든 탐색이 끝났을 경우

dfs 함수는 True를 반환하고 main 함수로 돌아갑니다.

블록의 수 뿐 아니라, 각 블록에 포함된 장애물의 수도 출력해야하므로,

obstacle 배열에 장애물의 수도 저장해줍니다.

이때, 장애물의 수를 저장하는 count 변수는 전역 변수로 선언되어

재귀 탐색에서 해당 변수에 장애물 수를 더해줍니다.

 

재귀 문제를 오랜만에 풀었더니 어렵게 느껴졌습니다. DFS 문제 좀 다시 많이 풀어봐야겠습니다.