[Python] 13265. 색칠하기

 

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

13265번: 색칠하기

접근법

• 입력을 받아 각 노드와 연결된 노드들을 담은 이중 배열을 생성
• bfs를 돌면서 노드들을 돌며 연결된 노드들을 들러봄
  • 색이 칠해지 않다면 current_node의 색과 다른 것으로 칠함
  • 색이 칠해져 있다면 current_node의 색과 다른지 비교하여 result return

from collections import deque
def bfs(x):
    global result

    que = deque()
    que.append(x)
    colored[x] = 1

    while que:
        cur_num = que.popleft()
        for circle in line_list[cur_num]:
            if colored[circle] == 0:
                colored[circle] = colored[cur_num] * -1
                que.append(circle)
            if colored[circle] == colored[cur_num]:
                result = "impossible"
                return

n = int(input())
for i in range(n):
    num_o, num_l = map(int, input().split())
    line_list = [[] for _ in range(num_o + 1)]
    colored = [0] * (num_o + 1)
    for i in range(num_l):
        n1, n2 = map(int, input().split())
        line_list[n1].append(n2)
        line_list[n2].append(n1)

    result = "possible"

    for i in range(1, num_o + 1):
        if colored[i] == 0:
            bfs(i)
            if result == "impossible":
                break
    print(result)

 

---

처음 생각했던 알고리즘 및 문제점

try1

return을 사용함으로써 5개 입력을 받아야 하지만, 3개만 입력받고 return될 경우 나머지 2개에 대해서 다음 입력으로 넘어가 에러를 일으킴. → return 대신 continue 활용

"""
queue를 활용해서 연결돼어있는 노드들을 모두 넣고, 앞에서부터 차례대로 색을 넣되
겹치는 색이 있는 순간 바로 impossible return
-> 굳이 queue에 저장할 필요가 있을까?
"""

def coloring():
    num_o, num_l = map(int,input().split())

    color = 1
    colored = [0]*(num_o + 1)
    for i in range(num_l):
        num_1, num_2 = map(int,input().split())
        if (i == 0) and (colored[num_1] == 0):
            colored[num_1] = color
            color *= -1
        if (colored[num_1] == colored[num_2]):
            print("impossible")
            return
        if (colored[num_1] != 0) and (colored[num_2] != 0):
            continue
        colored[num_2] = color * -1

    print("possible")


n = int(input())
for i in range(n):
    coloring()

---

try2

time out → input들을 모두 저장해서 queue를 활용하는 방법으로

def coloring():
    num_o, num_l = map(int,input().split())

    color = 1
    colored = {}
    answer = "possible"
    for i in range(num_l):
        num_1, num_2 = map(int,input().split())
        if num_1 not in colored.keys(): #num1은 없고 num2만 있는 경우는 어떻게..
            colored[num_1] = color
        if (num_1 in colored.keys()) and (num_2 in colored.keys()): # 둘다 색이 있는 경우
            if (colored[num_1] == colored[num_2]):
                answer = "impossible"
            continue
        colored[num_2] = colored[num_1] * -1
    print(answer)


n = int(input())
for i in range(n):
    coloring()

---

try3

timeout

from collections import deque
def bfs(x):
    global result
    global line_list
    que = deque()


    que.append(x)
    colored[x] = 1
    while que:
        cur_num = que.popleft()
        for circle in line_list[cur_num]:
            if colored[circle] == 0:
                colored[circle] = colored[cur_num] * -1
                que.append(circle)
            if colored[circle] == colored[cur_num]:
                result = "impossible"
                break

n = int(input())
for i in range(n):
    num_o, num_l = map(int, input().split())
    line_list = [[] for _ in range(num_o + 1)]
    colored = [0] * (num_o + 1)
    for i in range(num_l):
        n1, n2 = map(int, input().split())
        line_list[n1].append(n2)
        line_list[n2].append(n1)

    result = "possible"
    bfs(1)

    for i in range(num_o + 1):
        if colored[i] == 0:
            bfs(1)
    print(result)

 

사용된 알고리즘

그래프, 그래프탐색, 너비우선탐색, 깊이우선탐색