python 백준2667 단지번호붙이기(BOJ2667)

문제링크 : https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

dfs를 공부하면서 나왔던 예시문제와 비슷하다

상하좌우를 dx, dy로 해서 풀면 쪼금 더 짧게도 가능할것같다

#지도크기
n = int(input())

#단지 집 수가 담길 리스트
house_count = []

#입력으로 받는 지도 리스트
input_map = []

for _ in range(n):
  #지도에 추가
  input_map.append(list(map(int, input())))

def dfs(x, y):
  #지도를 벗어난다면 즉시 종료
  if x < 0 or x >= n or y < 0 or y >= n :
    return 0
  #해당 가구를 방문하지않았다면 방문처리
  if input_map[x][y] == 1:
    input_map[x][y] = 0
    #가구 수 +1
    count = 1

    #해당 가구 상하좌우로 탐색해서 가구수에 더하기
    count += dfs(x-1,y)
    count += dfs(x+1,y)
    count += dfs(x,y-1)
    count += dfs(x,y+1)
    return count
  return 0

#dfs 호출하면서 단지 정보 추가
for i in range(n):
  for j in range(n):
    count = dfs(i,j)
    if count != 0:
      house_count.append(count)

#단지 집 수 오름차순 정렬
house_count.sort()

#출력
print(len(house_count))
for i in range(len(house_count)):
  print(house_count[i])

근데 이런거 풀면서 웃긴게 문제의 출처다

2667번 문제 출처

정답률이 41%정도인데 이런 문제가 초등부 1번 문제라는거..

난 초등학교때 아파트 단지에서 경찰과 도둑이나 했지 dfs로 단지번호 붙이기라니.. 참..