코드

DFS

n = int(input())
graph = []

for _ in range(n):
    graph.append(list(map(int, input())))

# 아파트 개수
cnt = 0

# 아파트 개수를 담을 리스트
cnt_list = []
    
def dfs(x, y):
    # 상하좌우 방향 의미
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    # 지도 범위를 넘어서면 종료
    if x < 0 or x >= n or y < 0 or y >= n:
        return False
    
    # if graph[x][y] == 0 or graph[x][y] == 2:
    #     return False
    
    # 좌표값이 1인 경우 => 아파트가 존재하는 경우
    # 좌표값이 1이 아닌 숫자로 바꿔주고 (재방문 방지)
    # 아파트 개수를 1 증가
    if graph[x][y] == 1:
        graph[x][y] = 2
        global cnt
        cnt += 1
        
        # 상하좌우 방향으로 재귀적으로 탐색
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)
        return True
    return False

# 모든 좌표에 대해서 dfs 실행
for i in range(n):
    for j in range(n):
        if dfs(i, j):
            cnt_list.append(cnt)
            # 단지 별로 아파트 개수를 카운팅해야 하므로
            # 0으로 매번 초기화해줘야 한다
            cnt = 0

# 오름차순 조건
cnt_list.sort()            
print(len(cnt_list))
for c in cnt_list:
    print(c)

BFS

from collections import deque

n = int(input())
graph = []

for _ in range(n):
    graph.append(list(map(int, input())))
    
def bfs(x, y):
    q = deque()
    q.append((x, y))
    
    # 이 부분 중요
    graph[x][y] = 0
    cnt = 1
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    while q:
        x, y = q.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            
            if graph[nx][ny] == 1:
                graph[nx][ny] = 2
                q.append((nx, ny))
                cnt += 1
    return cnt    
        
cnt_list = []
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            cnt_list.append(bfs(i, j))
            
cnt_list.sort()
print(len(cnt_list))
for c in cnt_list:
    print(c)

문제 해설

DFS (BFS) 문제이다. 미로 찾기와 아이스크림 만들기가 합쳐져 있는 느낌의 문제.

DFS로는 전역 변수를 쓰기 싫어서 애쓰다가 참고할 코드 조차 대부분 전역 변수를 써서 일단 전역 변수로 처리하였다. 이 부분에선 보완을 해봐야겠다.

BFS 같은 경우

graph[x][y] = 0
    cnt = 1

이 부분을

cnt = 0

이렇게 구현하니 테스트 케이스는 정답이 인정됐는데 코너 케이스가 따로 있는 것인지 계속 오답 처리가 돼서 다른 분들 코드를 참고하니 모두 위에 코드처럼 작성하셨길래 따라 수정하니까 정답으로 인정됐다.

클래스 3 부분을 완료한 후에는 각 알고리즘 별로 문제를 풀어봐야겠다.

댓글남기기

참고