문제
자율주행팀 SW 엔지니어인 당신에게 장애물과 도로를 인식할 수 있는 프로그램을 만들라는 업무가 주어졌다.
[그림 1] 지도 예시
우선 [그림 1]과 같이 정사각형 모양의 지도가 있다. 1은 장애물이 있는 곳을, 0은 도로가 있는 곳을 나타낸다.
당신은 이 지도를 가지고 연결된 장애물들의 모임인 블록을 정의하고, 불록에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 장애물이 좌우, 혹은 아래위로 붙어 있는 경우를 말한다. 대각선 상에 장애물이 있는 경우는 연결된 것이 아니다.
[그림 2] 블록 별 번호 부여
[그림 2]는 [그림 1]을 블록 별로 번호를 붙인 것이다.
지도를 입력하여 장애물 블록수를 출력하고, 각 블록에 속하는 장애물의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
입력
입력 값의 첫 번째 줄에는 지도의 크기 N(정사각형임으로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.
출력
첫 번째 줄에는 총 블록 수를 출력 하시오.
그리고 각 블록 내 장애물의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.
예시
입력
7
1110111
0110101
0110101
0000100
0110000
0111110
0110000
Plain Text
복사
출력
3
7
8
9
Plain Text
복사
정답
import sys
from collections import deque
board = []
N = int(sys.stdin.readline())
# board 만들기
for i in range(N):
str_list = list(sys.stdin.readline())
num_list = []
for j in range(N):
num_list.append(int(str_list[j]))
board.append(num_list)
# 그룹 만들어주기
def group_change(board, start_y, start_x, g_index):
N = len(board)
g_num = 0 # 해당 그룹에 포함되어 있는 원소의 개수
dy = [-1,1,0,0]
dx = [0,0,-1,1]
visited = [[False]*N for _ in range(N)] # 방문 여부
dq = deque()
dq.append([start_y, start_x])
board[start_y][start_x] = g_index # 시작점 g_index로 변환
visited[start_y][start_x] = True # 방문 처리
g_num += 1 # 그룹 원소 개수 +1
while dq:
y, x = dq.popleft()
for i in range(4):
new_y = y + dy[i]
new_x = x + dx[i]
if (new_y < 0) or (new_y >= N) or (new_x < 0) or (new_x >= N): continue
if (board[new_y][new_x]!=1) or (visited[new_y][new_x] == True): continue
board[new_y][new_x] = g_index
visited[new_y][new_x] = True
dq.append([new_y,new_x])
g_num += 1
return g_num
# 전부 그룹화 시켰는지 여부 확인
def is_all_changed(board):
N = len(board)
for i in range(N):
for j in range(N):
if board[i][j] == 1:
return False
return True
# 1 위치 확인
def first_one(board):
N = len(board)
for i in range(N):
for j in range(N):
if board[i][j] == 1:
return [i,j]
return
def obstacles(board):
N = len(board)
answer = []
i = 2 # 그룹 인덱스 2부터 시작 (1은 이미 있으므로)
# 1이 전부 그룹화 될 때까지 계속
while is_all_changed(board) == False:
start_y, start_x = first_one(board)
answer.append(group_change(board, start_y, start_x, i))
i += 1
return sorted(answer)
answer_list = obstacles(board)
print(len(answer_list))
for answer in answer_list:
print(answer)
Python
복사
풀이
•
동계 테스트 시점 예측 문제와 거의 유사하다. 그래서 기본적으로 같은 방식을 사용하였다.
•
마찬가지로 BFS를 사용하였으며 1로 되어있는 값들을 전부 그룹별로 다른 number로 설정해주는 방식을 사용했다.
•
우선 시작점에서부터 연결되어있는 1의 값들을 전부 g_index로 변환해주는 함수를 작성하였다.
# 그룹 만들어주기
def group_change(board, start_y, start_x, g_index):
N = len(board)
g_num = 0 # 해당 그룹에 포함되어 있는 원소의 개수
dy = [-1,1,0,0]
dx = [0,0,-1,1]
visited = [[False]*N for _ in range(N)] # 방문 여부
dq = deque()
dq.append([start_y, start_x])
board[start_y][start_x] = g_index # 시작점 g_index로 변환
visited[start_y][start_x] = True # 방문 처리
g_num += 1 # 그룹 원소 개수 +1
while dq:
y, x = dq.popleft()
for i in range(4):
new_y = y + dy[i]
new_x = x + dx[i]
if (new_y < 0) or (new_y >= N) or (new_x < 0) or (new_x >= N): continue
if (board[new_y][new_x]!=1) or (visited[new_y][new_x] == True): continue
board[new_y][new_x] = g_index
visited[new_y][new_x] = True
dq.append([new_y,new_x])
g_num += 1
return g_num
Python
복사
→ 마지막 return 값은 해당 그룹에 속해있는 원소의 개수가 출력되도록 하였다.
•
그리고 1 값들이 전부 그룹화가 되어야 하기 때문에 1값이 남아있는지 확인하는 함수와 1값이 있다면 1값의 위치를 확인해주는 함수를 작성하였다. (이때 왼쪽위에서부터 오른쪽 아래로 훑으며 가장 먼저 나오는 1값의 위치를 반환)
# 전부 그룹화 시켰는지 여부 확인
def is_all_changed(board):
N = len(board)
for i in range(N):
for j in range(N):
if board[i][j] == 1:
return False
return True
# 1 위치 확인
def first_one(board):
N = len(board)
for i in range(N):
for j in range(N):
if board[i][j] == 1:
return [i,j]
return
Python
복사
•
이를 이용하여 이어져 있는 1값들을 전부 그룹화 시키고 각 그룹의 원소의 개수를 세서 정렬한 뒤 프린트하였다.
def obstacles(board):
N = len(board)
answer = []
i = 2 # 그룹 인덱스 2부터 시작 (1은 이미 있으므로)
# 1이 전부 그룹화 될 때까지 계속
while is_all_changed(board) == False:
start_y, start_x = first_one(board)
answer.append(group_change(board, start_y, start_x, i))
i += 1
return sorted(answer)
answer_list = obstacles(board)
print(len(answer_list))
for answer in answer_list:
print(answer)
Python
복사