문제 링크

https://www.acmicpc.net/problem/2667

풀이 방법

DPS를 이용하여 집이 있는 곳을 찾으면 동서남북 네 방향에 더 이상 집이 없을 때까지 계속 탐색하는 과정 진행. 탐색을 완료한 미로는 0으로 방문처리

코드 (python)

n = int(input())
maze = []
for i in range(n):
    maze.append(list(map(int, input())))
cnt = 0
stack = []
#상하좌우
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
res = []
for i in range(n):
    for j in range(n):
        if maze[i][j] == 1:
            area = 1
            maze[i][j] = 0 #방문처리
            stack.append([i, j]) #위치저장
            while stack:
                y, x = stack.pop()
                for k in range(4):
                    ny = y + dy[k]
                    nx = x + dx[k]
                    if (ny >= 0 and ny < n and nx >= 0 and nx < n) :
                        if maze[ny][nx] == 1:
                            area += 1
                            stack.append([ny, nx])
                            maze[ny][nx] = 0
            cnt +=1
            res.append(area)
print(cnt)
print('\n'.join(map(str,sorted(res))))

join

• 파이썬에서 리스트를 문자열로 일정하게 합쳐주는 함수
• ''.join(리스트) 혹은 '구분자'.join(리스트)
• 이 때 리스트의 요소들은 모두 문자열이어야 한다.
• 만약에 내가 문자열로 합치고자 하는 리스트의 원소들이 str이 아니라면? map을 이용한다.
• '.'.join(map(str, [1,2,3])) #리스트 각 원소를 map을 이용하여 str로 형변환하고 join

sorted vs sort

1. sorted

• sorted(리스트) 하면 리스트를 오름차순으로 정렬한 새로운 리스트를 전달해줌

2. sort

• 리스트에서 사용할 수 있는 리스트 method
• 리스트.sort 하면 리스트의 원본이 정렬됨 (default : 오름차순)