study/백준(BOJ)
[Python] 13265. 색칠하기
bbooo
2023. 4. 16. 02:01
728x90
https://www.acmicpc.net/problem/13265
13265번: 색칠하기
각 테스트 케이스에 대해서 possible 이나 impossible 을 출력한다. 2 가지 색상으로 색칠이 가능하면 possible. 불가능하면 impossible 이다.
www.acmicpc.net
접근법
- 입력을 받아 각 노드와 연결된 노드들을 담은 이중 배열을 생성
- 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)
사용된 알고리즘
그래프, 그래프탐색, 너비우선탐색, 깊이우선탐색
728x90