99클럽 TIL (240808)

[Middler] 단지 번호 붙이기

 

걸린시간 : 1시간

 

오늘의 회고

DFS/BFS로 풀어야한다는 것을 파악했으나, stack을 사용하려고 하다가 약간 헷갈렸던 것 같다.. DFS/BFS는 단골문제이니 템플릿을 정확히 익혀두도록 하자.

 

[DFS 동작 과정]

1. 탐색 시작 노드를 스택에 삽입하고 방문처리

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄.

3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

 

문제 풀이

1. python

재귀

# DFS 깊이우선탐색, stack을 활용하여 풀기.
# 계획
# 1. map을 돈다. 
#    방문하지 않 집인 경우, stack엥 넣는다.
# 2. stack을 확인한다. stack에 있는 집을 방문표시한다.
# 3. 더이상 같은 단지가 아니라면 단지수를 +1, 집의 개수를 answer에 넣고 초기화한다.

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

dx = [0, 1, 0, -1]
dy = [1, 0, -1 ,0]

stack = []
home = 0 # 집의 개수
town = 0 # 단지 개수
answer = [] # 각 단지별, 집 개수 리스트

def bfs(x,y) :
    visited[x][y] = True
    global home
    home += 1
    
    for d in range(4) :
        nx = x + dx[d]
        ny = y + dy[d]
        if nx < 0 or ny < 0 or nx >= N or ny >= N : continue
        
        if map[nx][ny] == 1 and not visited[nx][ny] :
            bfs(nx, ny)

for i in range(N) :
    for j in range(N) :
        if map[i][j] == 1 and not visited[i][j] :
            bfs(i,j)
            answer.append(home)
            town += 1
            home = 0
            
answer.sort()

print(town)
for i in answer :
    print(i)

 

스택

# DFS 깊이우선탐색, stack을 활용하여 풀기.
# 계획
# 1. map을 돈다. 
#    방문하지 않 집인 경우, stack엥 넣는다.
# 2. stack을 확인한다. stack에 있는 집을 방문표시한다.
# 3. 더이상 같은 단지가 아니라면 단지수를 +1, 집의 개수를 answer에 넣고 초기화한다.

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

dx = [0, 1, 0, -1]
dy = [1, 0, -1 ,0]


home = 0 # 집의 개수
town = 0 # 단지 개수
answer = [] # 각 단지별, 집 개수 리스트

for i in range(N) :
    for j in range(N) :
        if map[i][j] == 1 and visited[i][j] == False:
            stack = [[i,j]]
            town += 1
            home = 0
            
            while stack :
                [x, y] = stack.pop()
                visited[x][y] = True
                home += 1
                
                for d in range(4) :
                    nx = x + dx[d]
                    ny = y + dy[d]
                    if nx < 0 or ny < 0 or nx >= N or ny >= N : continue
                    
                    if map[nx][ny] == 1 and visited[nx][ny] == False:
                        stack.append([nx, ny])
                        visited[nx][ny] = True
            answer.append(home)
            
answer.sort()

print(town)
for i in answer :
    print(i)