[Softeer]장애물 인식 프로그램 파이썬 풀이

Softeer 장애물 인식 프로그램¶

문제 page: https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=409
전형적인 graph 탐색 알고리즘 문제이다.

1. 장애물이 1로만 표시되므로 그래프의 행과 열을 탐색하다 1이 나올경우 dfs 또는 bfs 알고리즘을 적용한다.
2. 탐색을 할 때 1이 나오면 count를 갱신해준다.
3. count를 list에 담는다.
4. list를 sort해서 print한다.
   두가지 방법
   1) sorted(list)
   2) list.sort()

dfs(using stack)¶

1. 초기화
   stack에 초기 노드의 x, y 좌표를 push한다.
   초기 노드를 방문 처리한다.

    cf) 방문 처리의 경우 여러가지가 있는데 여기서는 해당 graph의 값을 0으로 바꿔준다.(왜냐하면 graph의 값이 0인 경우는 애초에 방문하지 않으므로)

2. graph와 연결되어 있는 노드를 탐색한다 (문제의 경우 동서남북이 적합)
3. 1) if 탐색한 노드가 조건에 부합할 경우 해당 노드(좌표)를 stack에 push한다.
4. 2) else (탐색 결과) 조건에 부합한 노드가 없을 경우 탐색에 쓰인 좌표를 pop한다.
5. stack에 원소가 없을 때까지 반복한다.
   

사실 dfs는 재귀적으로 구현하는 것이 일반적으로 더 좋은 것 같다. (시간 복잡도 등)

In [ ]:

# 장애물 인식 프로그램
def dfs(Map, nx, ny):
    obstacle = 1
    move = [(-1, 0), (0, 1), (1, 0), (0, -1) ] # 북 동 남 서
    stack = []
    stack.append((nx, ny))
    Map[nx][ny] = 0
    while stack:
        nx, ny = stack[-1]

        for move_x, move_y in move:
            x = nx + move_x
            y = ny + move_y
            if x >= 0 and x < N and y >= 0 and y < N and Map[x][y] == 1:
                obstacle += 1
                nx = x
                ny = y
                stack.append((nx, ny))
                Map[nx][ny]=0
                break
            if (0, -1) == (move_x, move_y):
                stack.pop()
                
    return Map, obstacle

N = int(input())

graph = []
for _ in range(N):
    row_list = []
    row = input()
    for temp in row:
        row_list.append(int(temp))
        
    graph.append(row_list)
    
block=0
obstacles = []
for row in range(N):
    for col in range(N):
        if graph[row][col]==1:
            block += 1
            graph, obstacle = dfs(graph, row, col)
            obstacles.append(obstacle)

        
        
obstacles.sort()        
print(block)
for obstacle in obstacles:
    print(obstacle)