[백준][Python] 13265 색칠하기

그래프, bfs / 골드 5

🖍️

https://www.acmicpc.net/problem/13265

13265번: 색칠하기

 

 

내 풀이

 

from collections import deque

def bfs(c):
    q = deque()
    q.append(c)

    while q:
        current = q.popleft()

        if color[current] == '': # 현재 좌표의 색이 없다면, 연결된 동그라미들의 색을 확인한 후 결정해야 함
            b_count = w_count = 0
            for k in arr[current]:
                if color[k] == 'B':
                    b_count += 1
                elif color[k] == 'W':
                    w_count += 1
                
            if b_count > 0 and w_count > 0:
                return 'impossible'
            elif b_count > 0 and w_count == 0:
                color[current] = 'W'
            else:
                color[current] = 'B'


        for k in arr[current]:
            if color[k] == '': # 아직 색이 정해지지 않은 동그라미인 경우
                if color[current] == 'B':
                    color[k] = 'W'
                else:
                    color[k] = 'B'
                q.append(k)
            elif color[k] == color[current]: # 연결된 동그라미와 색이 같은 경우
                return 'impossible'
    return 'possible'


T = int(input())

for _ in range(T):
    n, m = map(int, input().split())
    arr = [[] for _ in range(n+1)]
    color = [''] * (n+1) # B or W

    for _ in range(m):
        n1, n2 = map(int, input().split())
        arr[n1].append(n2)
        arr[n2].append(n1)

    for i in range(1, n+1):
        if arr[i] != []:
            color[i] = 'B' # 시작
            s = i
            break

    ans = 0
    for i in range(s, n+1):
        if arr[i] != []:
            if bfs(i) == 'impossible':
                ans = 1

    if ans == 1:
        print('impossible')
    else:
        print('possible')

bfs(너비 우선 탐색)으로 풀었다.

 

 

코드 설명

 

arr: 각 동그라미와 연결된 동그라미들의 번호를 저장하는 이차원 리스트

color: 동그라미들의 색을 저장하는 리스트. 두 가지 색(Black or White) 중 하나가 된다.

arr = [[] for _ in range(n+1)]
color = [''] * (n+1) # B or W

 

연결되어 있는 동그라미 두 개의 번호를 받아,

각 리스트에 상대 동그라미의 번호를 추가한다.

for _ in range(m):
    n1, n2 = map(int, input().split())
    arr[n1].append(n2)
    arr[n2].append(n1)

 

ans: 2가지 색상으로 색칠이 가능한지, 불가능한지를 알려주는 변수 (0:가능, 1: 불가능)

 

1번 동그라미부터 시작하여 모든 동그라미를 검사하며,

리스트가 비어있지 않다면(해당 동그라미가 다른 동그라미와 연결되어 있다면) bfs를 호출한다.

ans = 0
for i in range(1, n+1):
    if arr[i] != []:
        if bfs(i) == 'impossible':
            ans = 1

 

 

✔️ bfs 함수 내

 

현재 동그라미의 색이 정해지지 않은 상태라면, 연결된 동그라미들의 색을 확인한 후 결정해야 한다.

 

b_count: B의 개수

w_count: W의 개수

 

1. B도 있고 W도 있는 경우

현재 동그라미는 둘 중 어떠한 색도 될 수 없다.

즉, 두 가지 색상으로 색칠이 불가능한 경우이므로, 'impossible'을 리턴한다.

 

2. B만 있는 경우

현재 동그라미는 W가 되어야 한다.

 

3. W만 있는 경우

현재 동그라미는 B가 되어야 한다.

 

4. B와 W 아무것도 없는 경우

현재 동그라미의 색을 B로 설정한다. (W로 설정해도 무관)

current = q.popleft()

if color[current] == '': # 현재 좌표의 색이 없다면, 연결된 동그라미들의 색을 확인한 후 결정해야 함
    b_count = w_count = 0
    for k in arr[current]:
        if color[k] == 'B':
            b_count += 1
        elif color[k] == 'W':
            w_count += 1

    if b_count > 0 and w_count > 0:
        return 'impossible'
    elif b_count > 0 and w_count == 0:
        color[current] = 'W'
    else:
        color[current] = 'B'

 

연결된 동그라미들을 검사한다.

아직 색이 정해지지 않은 동그라미인 경우, 현재 동그라미와 다른 색으로 설정해 준다.

현재 동그라미의 색과 연결된 동그라미의 색이 같다면, 두 가지 색상으로 색칠이 불가능한 경우이므로, 'impossible'을 리턴한다.

for k in arr[current]:
    if color[k] == '': # 아직 색이 정해지지 않은 동그라미인 경우
        if color[current] == 'B':
            color[k] = 'W'
        else:
            color[k] = 'B'
        q.append(k)
    elif color[k] == color[current]: # 연결된 동그라미와 색이 같은 경우
        return 'impossible'

 

 

🙀 간과했던 점

 

1. 무조건 1번 동그라미부터 검사하도록 했었는데, 1번 동그라미와 연결된 동그라미가 없을 수도 있다.

2. 연결된 동그라미들이 각각 떨어져서 존재할 수도 있다.

3. 현재 동그라미와 인접한 동그라미들의 색을 결정할 때, 현재 동그라미의 색이 정해지지 않은 경우를 고려하지 않았다.

 

 

✌🏻 해결 방법

 

[ bfs 호출 방식 변환 ]

before: bfs 한 번만 호출

after: for문을 돌면서 다른 동그라미와 연결되어 있는 동그라미를 발견했다면 bfs 호출

 

[ 현재 동그라미의 색이 정해지지 않은 경우 ]

연결된 동그라미들의 색을 검사하여 그 결과를 토대로 현재 동그라미의 색을 먼저 결정해주고 나서,

연결된 동그라미들의 색을 결정하도록 수정