[python 파이썬] 백준 2667번 단지번호붙이기

2667번: 단지번호붙이기

 

나는 코딩테스트 이론 공부를 '이것이 취업을 위한 코딩테스트다' 라는 책으로 하고 있다. 

 

이 2667번 문제는 DFS/BFS 챕터에 있던 음료수 얼려먹기문제(DFS)와 유사했다. (검색하면 나옴)

 

(음료수얼려먹기 문제 답)

n=int(input())

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

def dfs(x,y):
    #주어진 범위를 벗어나는 경우에 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= n:
        return False
    # 현재노드를 아직 방문하지 않았다면
    if graph[x][y]==0:
        #해당노드 방문처리
        graph[x][y]=1
        #상하좌우의 위치도 모두 재귀적으로 호출
        dfs(x-1,y)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x,y+1)

        return True
    return False

#모든 노드에 대해 음료수 채우기
result=0
for i in range(n):
    for j in range(n):
        #현재위치에서 dfs수행
        if dfs(i,j)==True:
            result+=1
print(result)

 

음료수 얼려먹기 문제와의 차이점은  뭉쳐있는 덩어리 개수를 세는 것 뿐 아니라 덩어리의 크기까지 나타내야헀다. 

따라서 음료수 얼려먹기문제에 count를 글로벌 변수로 추가하여 해결했다! 

 

(2667번 답)

n=int(input())

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



def dfs(x,y):
    global count  # 함수속에서 나온 count값을 밖에서 쓰기위해
    #주어진 범위를 벗어나는 경우에 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= n:
        return False
    # 현재노드를 아직 방문하지 않았다면
    if graph[x][y]==1:
        count+=1
        #해당노드 방문처리
        graph[x][y]=0
        #상하좌우의 위치도 모두 재귀적으로 호출
        dfs(x-1,y)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x,y+1)
        return True
    return False

result=0
count=0
danji=[]
result=0
for i in range(n):
    for j in range(n):
        #현재위치에서 dfs수행
        if dfs(i,j)==True:
            result+=1
            danji.append(count)
            count=0

print(result)
danji.sort() # 디폴트 오름차순
for d in danji:
    print(d)