BFS를 이용하여 캔디팡 구현하기
https://codeup.kr/problem.php?id=2605

22-06-02

BFS가 뭐지..?

Next what to do.
1. from collections import deque 활용
while queue 가 포인트라고 생각함.!

23-08-16

BFS로 해결! <- 검색함..

import numpy as np
from collections import deque


candi_matrix =[]
n,m = 7,7

for i in range(n):
    candi_matrix.append(list(input().split(" ")))
    
Graph = {}

for i in range(n):
    for j in range(m):
        
        node = candi_matrix[i][j]
        
        connected_nodes = []
        if i > 0:
            if candi_matrix[i-1][j] == node:
                connected_nodes.append((i-1,j))
        if j > 0:
            if candi_matrix[i][j-1] == node:
                connected_nodes.append((i,j-1))
        if i < n-1:
            if candi_matrix[i+1][j] == node:
                connected_nodes.append((i+1,j))
        if j < m-1:
            if candi_matrix[i][j+1] == node:
                connected_nodes.append((i,j+1))
        
        if len(connected_nodes)>0:
            Graph[(i,j)] = connected_nodes
            
 def bfs(G, start_point):
    visited = list() # 방문한 노드를 담을 배열
    queue = list() # 방문 예정인 노드를 담을 배열

    queue.append(start_point) # 처음에는 시작 노드 담아주고 시작하기.

    while queue: # 더 이상 방문할 노드가 없을 때까지.
        node = queue.pop(0) # 방문할 노드를 앞에서 부터 하나싹 꺼내기.

        if node not in visited: # 방문한 노드가 아니라면
            visited.append(node) # visited 배열에 추가
            queue.extend(Graph[node]) # 해당 노드의 자식 노드로 추가

    #print("bfs - ", visited)
    
    return visited
    
visited_nodes = []
candi_pop = 0
while len(visited_nodes) < len(Graph.keys()):
    
    
    start_point = list(set(Graph.keys())- set(visited_nodes))[0]
    connected_nodes = bfs(Graph,start_point)
    
    if len(connected_nodes) >= 3:
        candi_pop += 1
        
    visited_nodes += list(set(connected_nodes) & set(Graph.keys()))
    
print(candi_pop)

Next what to do
1. BFS 검색없이 사용!