작심 큰일 챌린지 - 초콜릿 괴도 코코 (Sweet) (파이썬)

새로 배운 개념이나 기술:
남은 노드들이 모두 연결이 되어 있지만 사이클이 없으려면 트리 구조를 이루어야 한다. 트리 구조는 무방향 그래프에서 모든 노드가 사이클 없이 연결되어 있고, v(노드 수)-e(간선 수) == 1로 확인할 수 있다.
1개였던 덩어리에서 2개 이상으로 덩어리가 끊어졌는지 아닌지를 확인하기 위해선 bfs를 돌리면서 방문한 노드의 수와 원래 덩어리 수를 비교해보면 알 수 있다.
bfs 돌릴 때) 남아 있는 초콜릿들을 빠르게 조회하기 위해 set을 사용할 수 있고 대신 set은 순서가 보장되지 않은 자료 구조니까 리스트처럼 인덱스를 사용해 첫 원소를 q에 넣어줄 수 없고 next(iter(remaining)을 써야 한다.

어려웠던 점과 해결 방법:
조건1과 조건2를 모두 만족하도록 코드를 짜는 것이 어려웠다. 아무래도 조건이 많아 지면 구현이 복잡해지니까 덜컥 겁을 먹는 것 같은데 앞으로는 만족해야 하는 조건을 한꺼번에 만족하도록 구현하는 것 보다 하나 하나 만족하도록 단계적으로 코드를 작성한 후 결과적으로 조건들을 모두 만족하도록 짜야 겠다고 생각했다.

 

 

import sys
input = sys.stdin.readline
from collections import deque
def solution():
    n = int(input())
    board = [list(input().strip()) for _ in range(n)]
    # 사이클을 가능하게 하는 지점을 떼어내야 조건을 만족할 수 있다.

    # 1. 초콜릿들 위치 저장
    chocolates = []
    for i in range(n):
        for j in range(n):
            if board[i][j] == '#':
                chocolates.append((i, j))
    
    choco = len(chocolates)
    answers = []
    # 2. 각 초콜릿을 한 번씩 떼어보는 시뮬레이션
    for i in range(choco):
        removed = chocolates[i]

        # 떼어낸 후 남은 초콜릿들의 집합 (빠른 조회를 위해 set사용)
        remaining = set(chocolates)
        remaining.remove(removed)

        # 조건1. 연결성 확인 (bfs)
        directions = [(0,1), (0,-1), (1,0), (-1,0)]
        # remaining이 set이라 순서가 없으니 맨 앞 하나 꺼내려면 이렇게 해야 한다.
        start = next(iter(remaining))
        q = deque([start])
        visited = {start}
        while q:
            x, y = q.popleft()
            for dx, dy in directions:
                nx, ny = dx+x, dy+y
                if (nx, ny) in remaining and (nx, ny) not in visited:
                    visited.add((nx, ny))
                    q.append((nx, ny))

        # bfs 후 방문한 개수가 남은 초콜릿 수와 다르면 조각이 나뉜 것
        if len(visited) != len(remaining):
            continue

        # 조건2. 사이클 확인 (v-e=1)
        v = len(remaining)
        e = 0
        # 간선 개수 세기 (중복 방지를 위해 오른쪽, 아래쪽만 확인)
        for x, y in remaining:
            if (x, y+1) in remaining: # 오른쪽 확인
                e += 1
            if (x+1, y) in remaining: # 아래쪽 확인
                e += 1
        
        # 연결 그래프가 트리이려면 v-e=1 이어야 한다.
        if v-e == 1:
            # 두 조건 모두 만족시 정답에 추가 (좌표는 1based index)
            answers.append((removed[0]+1, removed[1]+1))
    
    # 최종 출력
    print(len(answers))
    for x, y in answers:
        print(x, y)

solution()