[Softeer] 장애물 인식 프로그램 (level 2)

사용 언어: Python3

문제

장애물 인식 프로그램

풀이

나의 풀이

import sys

dx, dy = [0,-1,0,1], [1,0,-1,0]
def DFS(x, y):
    global cnt
    visited[x][y] = 1
    cnt += 1
    for w in range(4):
        xx, yy = x+dx[w], y+dy[w]
        if xx<0 or xx>=N or yy<0 or yy>=N:
            continue
        if board[xx][yy] == 0 or visited[xx][yy]:
            continue
        DFS(xx, yy)

N = int(input())
board = [list(map(int, input())) for _ in range(N)]
visited = [[0] * N for _ in range(N)]

res = []
for i in range(N):
    for j in range(N):
        if board[i][j] == 0 or visited[i][j]:
            continue
        cnt = 0 # 매번 리셋 # 각각의 blood fill 그룹 안에 몇 개의 칸이 있는지
        DFS(i, j)
        res.append(cnt)

res.sort()
print(len(res))
for x in res:
    print(x)

• 테스트 케이스: 성공
• 제출 결과: 성공

나의 풀이 (230727 추가)

N = int(input())
board = [list(map(int, input())) for _ in range(N)]
visited = [[0] * N for _ in range(N)]


dx, dy = [0,-1,0,1], [1,0,-1,0]
def DFS(x, y):
    global cnt
    visited[x][y] = 1
    cnt += 1
    for w in range(4):
        xx, yy = x+dx[w], y+dy[w]
        if xx<0 or xx>=N or yy<0 or yy>=N:
            continue
        if board[xx][yy] == 0 or visited[xx][yy]:
            continue
        DFS(xx, yy)

ans = []
for i in range(N):
    for j in range(N):
        if board[i][j] == 0 or visited[i][j]:
            continue
        cnt = 0
        DFS(i, j)
        ans.append(cnt)

ans.sort() # ✅ 오름차순 주의 !!
print(len(ans))
print(*ans, sep='\n')

• 테스트 케이스: 성공
• 제출 결과: 성공
• print(*): 리스트 원소나 문자열 각각의 문자를 한 칸 씩 띄워 출력한다.
  

  ans = [1, 2, 3]
  print(*ans) # 1 2 3
  

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기