[softeer] 소프티어(파이썬): 장애물 인식 프로그램 ★★

문제

Softeer

- 정사각형 모양의 지도가 있는데 이 지도에는 1은 장애물이 있는 곳을, 0은 도로가 있는 곳을 나타낸다.

- 지도에 연결된 장애물들의 모임인 블록을 정의하고, 블록에 번호를 붙이려고 한다.

- 장애물은 좌우, 아래위로만 연결할 수 있고 대각선 상에 장애물은 연결할 수 없다.

- 장애물 블록수를 구하고 각 블록에 속하는 장애물의 수를 오름차순으로 정렬하여 출력하는 문제이다.

- 지도의 크기가 N(정사각형임으로 가로와 세로의 크기는 같다.)일때  5 ≤ N ≤ 25인 정수이다.

알고리즘

이 문제는 DFS(깊이 우선 탐색)을 이용하여 해결하는 문제이다. DFS는 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 문제에서 장애물의 블록은 좌우, 아래위로만 연결될 수 있다고 했으므로 그래프 형태로 모델링할 수 있다. 특정 지점에서 DFS를 수행하여 이동 가능한 모든 경로에 방문처리를 진행하고 조건에 따라 이동이 안되도록 처리를 하게 되면 방문처리가 된 지점을 블록으로 만들 수 있게 된다.

- 특정 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '1'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.

- 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 진행하는 과정을 반복하면, 연결된 모든 지점을 방문할 수 있다.

- 모든 노드에 대하여 위 과정을 반복하며, 방문하지 않은 지점의 수를 카운트한다.

- 리스트 변수를 통해 해당 노드를 방문하면 append를 해주어 장애물의 개수를 체크한다.

- 한 블록의 방문이 끝나면 리스트 변수의 길이를 다른 리스트 변수에 넣어 개수를 확인한다.

코드

import sys

# DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
def dfs(x, y):
    # 주어진 범위를 벗어나는 경우에 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= n:
        return False
    # 현재 노드를 아직 방문하지 않았다면
    if graph[x][y] == 1:
        # 장애물의 개수 체크
        cnt.append(1)
        # 해당 노드 방문 처리
        graph[x][y] = 0
        # 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)
        return True
    return False


# 지도 크기를 입력받는다.
n = int(sys.stdin.readline())
cnt = []
# 2차원 리스트의 맵 정보 입력 받는다.
graph = []
for i in range(n):
    graph.append(list(map(int, input())))
# 모든 노드(위치)에 대하여 장애물 블록을 만든다.
result = 0
result_list = []
for i in range(n):
    for j in range(n):
        # 현재 위치에서 DFS 수행
        if dfs(i, j) == True:
            result += 1
            # 길이를 통해 장애물의 개수 확인
            result_list.append(len(cnt))
            cnt = []

# 총 블록의 수 출력
print(result)
# 장애물의 수 오름차순 정렬 후 출력
result_list.sort()
for i in result_list:
    print(i)

결과

위 코드에서 if dfs(i,   j) == True: 밑에 print(graph)를 작성하면 해당 그래프의 방문처리를 출력 화면과 같이 확인할 수 있다.

<출력화면>

위 출력 화면을 보게 되면 첫 줄에 왼쪽에 있는 장애물들을 블록으로 만들고 0으로 초기화해주어 1이 사라지고 0으로 바뀐 것을 확인할 수 있고 두 번째 줄에는 오른쪽에 있는 장애물들을 블록으로 만들고 0으로 초기화해주어 1이 사라지고 0으로 바뀐 것을 확인할 수 있다. 그리고 마지막으로 밑에 있는 장애물들을 블록으로 만들고 0으로 초기화해주어 모드다 0으로 바뀐 것을 확인할 수 있다. 

따라서 코드를 분석하게 되면 DFS를 통해 이동 가능한 모든 경로를 방문 처리하고 장애물을 발견하면 해당 지점을 방문하게 된다. 또, 해당 지점 주변에도 장애물이 있는지 재귀적으로 DFS를 호출하여 방문처리를 하면 장애물 블록이 완성된다.

github

junjange/CodingTest