백준 13265 - 색칠하기

문제설명

제한사항 및 입출력

풀이

두 가지 색상으로 노드를 칠하는데 색상이 연속되지 않도록 칠하는 문제이다.

생각해보면 사이클이 없다면 두 가지 색상이 겹칠 일이 없다. 불가능한 경우는 사이클이 있고 사이클 내부 노드의 개수가 홀수인 경우이다.

하지만 이런 복잡한 조건을 생각하지 않아도 그래프를 탐색하며 1, 2로 칠해나가다가 다음 노드가 이번 노드와 같은 색이라면 불가능! 이라고 판단하면 된다.

그리고 모든 노드를 출발지점으로 고려해보아야한다. 주어진 노드가 전부 연결되어있지 않은 경우가 있기 때문에 여러 그래프가 생겼을 때 모든 그래프를 확인해야한다. (이거 고려 안 했다가 한 번 틀렸다..)

내 코드

bfs 풀이

def bfs(start, visited):
    queue = deque([start])
    visited[start] = 1
    
    while queue:
        x = queue.popleft()
        
        for nx in graph[x]:
            if visited[nx] == visited[x]:
                return "impossible"
            if not visited[nx]:
                queue.append(nx)
                visited[nx] = 2 if visited[x] == 1 else 1
            
    return "possible"
    
    
t = int(input())
for _ in range(t):
    n, m = mis()
    
    graph = [[] for _ in range(n+1)]
    for i in range(m):
        a, b = mis()
        graph[a].append(b)
        graph[b].append(a)
    
    visited = [0] * (n + 1)
    ans = bfs(1, visited)
    if ans == "possible":
        for i in range(1, n+1):
            if not visited[i]:
                ans = bfs(i, visited)
    
    print(ans)

dfs풀이

def dfs(x, color):
    visited[x] = color
    
    for nx in graph[x]:
        if visited[nx] == color:
            return False
        
        if not visited[nx]:
            if not dfs(nx, 3 - color):
                return False
    
    return True
    
    
t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    
    visited = [0] * (n + 1)
    ans = "possible"
    for i in range(1, n+1):
        if not visited[i]:
            if not dfs(i, 1):
                ans = "impossible"
                break
    
    print(ans)

역시 dfs가 함수 호출 오버헤드로 인해 시간이 조금 더 걸리는 것 같다.

 

• 그래프 생성: O(n + m)
• bfs/dfs 탐색: O(n + m) -> 방문하지 않은 정점에 대해서만 추가로 bfs를 실행하기 때문에 시간복잡도는 변하지 않는다.

시간 복잡도: O(n + m)

고찰

그래프 내부에서 사이클을 찾고 해당 사이클 노드의 개수가 홀수인지 판별하여 풀이할 수도 있을 것 같은데...