백준 2653 - 안정된 집단

www.acmicpc.net/problem/2653

2653번: 안정된 집단

그래프에서 서로 다른 집단을 찾고 그 집단에 속한 모든 노드들을 출력하면 되는 문제다. 해결법은 다음과 같다.

1. 방문 안한 노드를 찾고 거기에서 그 노드와 연결된 모든 노드를 찾는다.

    ex. 1번 노드를 방문 안했고 1번 노드에 연결된 노드들은 2, 3, 4이다. -> (1, [2, 3, 4])

2. bfs에 1번에서 했던 작업의 결과로 나온 것을 넣어준다.

3. 전 단계에서 연결된 노드를 탐색하며 1번의 연결된 결과와 같은 꼴로 연결되어 있는지 확인한다. 

4. 결과를 출력한다.

 

주의할 점은 다음과 같다.

1. 현재 자신과 연결된 없으면 0출력

2. 처음에 넣어준 연결된 노드와 값이 같지 않으면 0출력

 

import sys
from queue import Queue

arr = [[0 for col in range(101)] for row in range(101)]
visit = [0 for col in range(101)]
ans = []

def solution(x, n, love):
  q = Queue()
  q.put([x, love])
  
  while not q.empty():
    head = q.get()
    headNode = head[0]
    headLove = head[1]
    
    visit[headNode] = x

    for loveItem in headLove:
      if not visit[loveItem]:
        visit[loveItem] = x
        temp = []

        for i in range(1, n + 1):
          if arr[loveItem][i] == 0:
            temp.append(i)
        if headLove != temp:
          return False
        q.put([loveItem, temp])
  
  return True


if __name__ == "__main__":
  cnt = 0
  n = int(input())
  for i in range(1, n + 1):
    num = list(map(int, input().split()))
    for j in range (0, len(num)):
      arr[i][j + 1] = num[j]

  for i in range(1, n + 1):
    if visit[i] == 0:
      love = []
      for j in range(1, n + 1):
        if arr[i][j] == 0:
          love.append(j)
      if len(love) == 1:
        print(0)
        sys.exit()
      check = solution(i, n, love)
      if not check:
        print(0)
        sys.exit()
      else:
        ans.append(love)
        cnt += 1

  print(cnt)
  for ansItem in ans:
    for num in ansItem:
      print(num, end = ' ')
    print()