[Python] 단지번호붙이기 - BFS / DFS

문제 - 2667

해당 문제 링크

정답 - BFS

from collections import deque

# 상하좌우
# 상(-1, 0) 하(1, 0) 좌(0, -1) 우(0, 1)
dx=[-1, 1, 0, 0]
dy=[0, 0, -1, 1]

def bfs(x, y):
    
    q=deque()
    q.append((x, y))
    maps[x][y]+=1
    k=1

    while(q): # queue가 빌 때까지 반복
        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 maps[nx][ny] ==1:
                k+=1
                maps[nx][ny] = maps[x][y] +1
                q.append((nx, ny))

    return k


n=int(input())
maps=[]
for i in range(n):
    maps.append(list(map(int, input())))


answer=[]

for i in range(n):
    for j in range(n):
        if(maps[i][j]==1): #집이 있는 곳만 세기
            answer.append(bfs(i, j))

answer.sort() #오름차순으로 정렬

print(len(answer))
for i in range(len(answer)):
    print(answer[i])

정답 - DFS

from collections import deque

# 상하좌우
# 상(-1, 0) 하(1, 0) 좌(0, -1) 우(0, 1)
dx=[-1, 1, 0, 0]
dy=[0, 0, -1, 1]

def dfs(x, y):
    
    if x<0 or x>=n or y<0 or y>=n:
        return 0

    if maps[x][y]==1:
        global k
        k+=1
        maps[x][y]=0
        for i in range(4):
            nx = x+dx[i]
            ny= y+dy[i]
            dfs(nx, ny) #재귀함수
        return 1
    return 0
    


n=int(input())
maps=[]
num=[]

for i in range(n):
    maps.append(list(map(int, input())))

k=0
result=0

for i in range(n):
    for j in range(n):
        if(dfs(i, j)==1): #집이 있는 곳만 세기
            num.append(k)
            result+=1
            k=0

num.sort()
print(result)
for i in range(len(num)):
    print(num[i])

DFS 코드 참고 사이트

풀이

앞 서 푼 문제[게임 맵 최단거리]와 비슷해서 이를 이용해서 문제를 해결했다.

maps[i][j]==1일때 즉 집이 있는 곳에서부터 시작하고자 했을 때 BFS로 단지 수를 센다.

BFS 기본 동작 원리대로 진행한다.

구체적인 동작은 주석으로 처리하였다.

코드를 작성하면서 조심해야하는 부분이 있었다.

조심해야 할 부분

• 오름차순으로 정렬
  list.sort() : list 객체 자체를 정렬해주는 함수
  a=sorted(list) : 정렬된 리스트를 생성해주는 함수

• 조건을 집이 있는 곳을 가장 먼저 들리도록 if문으로 달았기 때문에 처음 bfs()함수를 들어갔을 때 큐에 처음 집이 있는 곳의 좌표를 넣는 것과 동시에 map[x][y]+=1 로 들린 곳에 값을 추가해주고, 단지 수를 세는 변수인 k를 1로 시작한다.

• 처음 코드를 작성했을 때는 visited 변수로 visited=[[0] n] n와 같이 초기화 하고, 방문 체크를 1값을 넣으면서 하려고 헀는데 그렇게 할 필요 없이 집이 있는 곳만 방문할 수 있게 maps[i][j] ==1로 확인할 수 있기 때문에 없애버렸다. 또한, 성능이 떨어지기 때문이다.

• [게임 맵 최단거리]와 다른 점
  : 앞에서 푼 문제와 비슷해서 이를 이용했는데
  여기서 그대로 따라하면 안됐다.
  앞의 문제는 어디를 도달할지가 나와있기 때문에 1씩 더해주면서 세주고 센 값을 배열 값으로 리턴하지만, 이 문제는 어디까지 도달하는지도 모르고 일단 세보는 것이기 때문에 반환하는 값을 직접 세줘야 했다. 그렇기 때문에 1을 미리 더해놓고 시작해놓는 것도 있는 것이다.
  다른 사람의 코드를 보니 지나간 자리는 0으로 메꾸는 방법이 있었다. 앞선 문제와 같이 더해주는 방식보다는 0으로 돌려놓는 게 좋을 것 같다. 기존에 풀었던 방식도 1보다 추가로 더 해주는 것이기 때문에 틀린 부분은 없지만, 더한 값을 '게임 맵 최단거리' 문제와 다르게 사용하지 않기 때문이다.
  0으로 돌려놓으면, 코드는 아래와 같다. 이 코드 또한 정답이다!

from collections import deque

# 상하좌우
# 상(-1, 0) 하(1, 0) 좌(0, -1) 우(0, 1)
dx=[-1, 1, 0, 0]
dy=[0, 0, -1, 1]

def bfs(x, y):
    
    q=deque()
    q.append((x, y))
    maps[x][y]=0
    k=1

    while(q): # queue가 빌 때까지 반복
        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 maps[nx][ny] ==1:
                k+=1
                maps[nx][ny] = 0
                q.append((nx, ny))

    return k


n=int(input())
maps=[]
for i in range(n):
    maps.append(list(map(int, input())))


answer=[]

for i in range(n):
    for j in range(n):
        if(maps[i][j]==1): #집이 있는 곳만 세기
            answer.append(bfs(i, j))

answer.sort() #오름차순으로 정렬

print(len(answer))
for i in range(len(answer)):
    print(answer[i])