문제
풀이
이코테 음료수 얼려먹기 문제와 완전히 똑같은 방식의 문제이다.
bfs와 dfs 두 방식으로 모두 풀이 가능하지만, 본인은 dfs 방식이 더 편하기 때문에 dfs 방식으로 풀이했다. 코드는 아래와 같다.
import sys
input = sys.stdin.readline
n = int(input())
arr = [list(map(int, input().strip())) for _ in range(n)]
visited = [[0] * n for i in range(n)]
homeNum = 0 # 하나의 단지에 집이 몇개 있는 지 셈
def dfs(x, y):
global homeNum
if x < 0 or y < 0 or x >= n or y >= n: # 범위를 벗어나면 fasle
return False
if arr[x][y] == 1 and visited[x][y] != 1: # 방문하지 않았으며 집일 경우
visited[x][y] = 1
homeNum += 1
dfs(x + 1, y)
dfs(x - 1, y)
dfs(x, y - 1)
dfs(x, y + 1)
return True
return False
result = []
for i in range(n):
for j in range(n):
if dfs(i, j):
result.append(homeNum)
homeNum = 0
print(len(result))
result.sort()
for i in range(len(result)):
print(result[i])
2차원 리스트 형태의 배열 arr 생성해 집과 벽의 정보를 저장해두고, 방문 확인을 위한 visited 리스트도 arr 크기와 동일하게 생성하여 0으로 초기화한다.
arr를 순차적으로 돌면서 dfs를 실행한다. dfs는 재귀적으로 동작하는데,
일단 인덱스 범위를 벗어나는 경우엔 조건 처리를 하여 바로 false값을 반환하도록 한다.
범위를 벗어나지 않는다면, 해당 인덱스 칸에 집이 존재하는 지 확인함과 동시에 방문 하지 않았던 집인지를 체크한다. (다른 풀이를 보니 집이 존재하는 칸이라면 값을 0으로 만들어 집을 없애는 방식으로도 많이 풀이하였다. 이렇게 하면 별도의 visited 리스트가 필요하지 않게 되므로 더 효율적인 방식같다)
조건을 충족한다면 집 하나를 성공적으로 확인한 것이므로 homeNum에 1을 더한다. homeNum은 하나의 단지에 집이 몇개 있는 지 카운트하는 변수이다. 이후 상하좌우로 dfs()를 순차적으로 호출한다. 재귀가 끝나면 최종적으로 True가 반환된다. 다시 아래의 for문으로 넘어가보자.
True값이 반환되었다는 뜻은 단지 하나가 완성되었다는 뜻으로 해석할 수 있다.
따라서 현재 homeNum을 result 리스트에 추가해주고, homeNum은 다음 단지의 카운트를 세기 위해 0으로 초기화해준다.
for문이 완료되면 result에는 각 단지별 집의 개수들이 저장되어있을 것이다. 이를 최종적으로 sort()하여 출력해주면된다. (+result의 길이와 함께!)
_
bfs보다 dfs가 훨씬 이해하기 쉽다. dfs 편식 중 .. 안 좋은 습관인 것 같다.
