softeer, 장애물 인식 프로그램

softeer, 장애물 인식 프로그램

 

문제

https://softeer.ai/practice/info.do?idx=1&eid=409 

Softeer

 

풀이

pass

 

풀이

일단 방문했으면 방문여부를 표시해야 재방문하는 일이 없을 것이다.

2차원 region이 주어졌으면 index범위를 벗어나지 않는지도 체크해 봐야 한다.

대각선 방향은 고려하지 않아도 되므로 북동남서를 탐색했을 때, '1'이고 방문한 적 없을 경우에만 탐색한다.

우리가 원하는 값은 방문가능한 범위 카운트한 값이다. 그래서 이를 global 변수로 둔다.

# 북동남서
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

def dfs(r,c):
    global cnt

    board[r][c] = 'v' # 방문표시
    cnt += 1

    for i in range(4):
        nr, nc = r + dr[i], c + dc[i]
        if 0 <= nr < N and 0 <= nc < N and board[nr][nc] == '1':
            dfs(nr, nc)

 

방문 표시후, 북동남서를 탐색! 방문가능하면 방문하게끔 코드를 짰다.

 

전체 코드

import sys
input = sys.stdin.readline

N = int(input())
# N = 7

board = []
# board = [['1', '1', '1', '0', '1', '1', '1'], ['0', '1', '1', '0', '1', '0', '1'], ['0', '1', '1', '0', '1', '0', '1'], ['0', '0', '0', '0', '1', '0', '0'], ['0', '1', '1', '0', '0', '0', '0'], ['0', '1', '1', '1', '1', '1', '0'], ['0', '1', '1', '0', '0', '0', '0']]
for _ in range(N):
    board.append(list(input()))

# 북동남서
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

def dfs(r,c):
    global cnt

    board[r][c] = 'v' # 방문표시
    cnt += 1

    for i in range(4):
        nr, nc = r + dr[i], c + dc[i]
        if 0 <= nr < N and 0 <= nc < N and board[nr][nc] == '1':
            dfs(nr, nc)

result = []
for r in range(N):
    for c in range(N):
        if board[r][c] == '1':
            cnt = 0
            dfs(r,c)
            result.append(cnt)  

result.sort()
print(len(result))
print(*result, sep='\n')