[Algorithm] Softeer 장애물 인식 프로그램 (Python)

[ Softeer 연습문제 - 장애물 인식 프로그램 ]

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

• 문제명 : 장애물 인식 프로그램
• 사용언어 : Python
• 알고리즘 : DFS/BFS -> 필자는 BFS 사용으로 풀이.

---

 

  문제

 

 

  알고리즘 및 풀이

이 문제는 이진 행렬에서 그룹의 개수와 각 그룹의 크기를 찾는 문제이다. 

필자는 BFS(너비 우선 탐색) 알고리즘을 활용했다. 큐를 활용하여 한 정점에서 시작하여 인접한 정점을 탐색하는 방법으로 접근하였다.

(x, y) 좌표를 순회하면서 "1"인 곳을 발견하면 해당 좌표에서 BFS를 시작하고

발견된 좌표는 방문 처리를 위해  "0"으로 바꿔준다. 이는 그룹의 크기를 측정하는 중복 방문을 방지한다.

 

- 전역 변수 활용 : 'cnt' 변수는 그룹의 크기를 저장하는데 활용되며, 'global' 키워드를 통해 전역 변수로 선언되어 함수 간에 값을 공유한다. 

 

import sys
from collections import deque


def bfs(x,y):
    global cnt
    
    # 상하좌우 방향 설정
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    queue = deque([[x,y]])

    while queue:
        x, y = queue.popleft()

        # 상하좌우 탐색
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
    
    		# 범위 검사
            if 0 <= nx < N and 0 <= ny < N:
                if map[nx][ny] == "1":
                    map[nx][ny] = 0
                    queue.append([nx,ny])
                    cnt += 1

# 입력 받기
N = int(sys.stdin.readline())
map = [list(sys.stdin.readline().rstrip()) for _ in range(N)]
answer = []

# 모든 좌표에 대해서 1인 지점을 찾아 BFS 수행
for i in range(N):
    for j in range(N):
        if map[i][j] == '1':
            map[i][j] = '0'    # 방문 처리
            cnt = 1
            bfs(i,j)
            answer.append(cnt)

# 정답 출력
answer.sort()
print(len(answer))          # 그룹의 개수 출력
print(*answer, sep = "\n")  # 각 그룹의 크기 출력

 

  결과

 

 

 

---

 

 

▼ 이래저래 풀이를 참고하다가 알았는데 백준 2667번:단지번호붙이기 와 동일한 문제이다.  

2667번: 단지번호붙이기