[백준 문제] 2667번 단지번호붙이기 (파이썬)


[백준 문제] 2667번 단지번호붙이기 (파이썬)

문제풀이

  • BFS로 풀었는데 다음에는 DFS로도 풀어보려한다.
  • 두가지만 기억하면 되는데 먼저 첫 시작점을 찾고, 그 시작점에서 BFS로 단지번호를 물들인다. 또 시작점 찾고 물들인다. 이렇게 풀면된다.
# 데이터 입력
n = int(input())
a = [list(map(int,list(input()))) for _ in range(n)]
d = [[0]*n for _ in range(n)]

# cnt(단지번호)와 dx, dy로 이루어진 아래 위 오른 왼 방향
cnt = 0
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# bfs를 이용해서 싹 다 그 단지번호로 지정해주기
def bfs(x, y, cnt) :
    d[x][y] = cnt;
    queue = [[x,y]]
    
    while queue :
        current_node = queue.pop(0)
        for k in range(4) :
            nx = current_node[0]+dx[k] ;
            ny = current_node[1]+dy[k] ;
            if (0 <= nx and nx < n) and (0 <= ny and ny < n) :
                if a[nx][ny] == 1 and d[nx][ny] == 0 :
                    queue += [[nx, ny]] ;
                    d[nx][ny] = cnt

# 첫 지역을 찾아서 bfs로 단지번호 지정해주고 또 다음 지역을 찾아서 지정해주는식
for i in range(n) :
    for j in range(n) :
        if a[i][j] == 1 and d[i][j] == 0 :
            cnt += 1
            bfs(i, j, cnt)

# 2차원을 1차원 리스트로 바꿔주기
answer = []
for i in d :
    answer += i

# 답 구해주기 (총 단지수랑 단지의 수를 sorting해서 출력하기)
print(max(answer))
arr = []
for x in range(1,max(answer)+1) :
    sum = 0
    for i in answer :
        if x == i :
           sum += 1
    arr.append(sum)

for _ in range(max(answer)) :
    arr.sort()
    
for i in arr :
    print(i)

3
7
8
9

# 얘는 그냥 잘 되었나 찍어보기~
d
[[0, 1, 1, 0, 2, 0, 0],
 [0, 1, 1, 0, 2, 0, 2],
 [1, 1, 1, 0, 2, 0, 2],
 [0, 0, 0, 0, 2, 2, 2],
 [0, 3, 0, 0, 0, 0, 0],
 [0, 3, 3, 3, 3, 3, 0],
 [0, 3, 3, 3, 0, 0, 0]]





© 2018. by statssy

Powered by statssy