[TIL] 그래프 문제 문제 풀이

1. 그래프 문제 풀이(DFS)

1. 1707번 - 이분 그래프

1. 이분 그래프(bipartite graph)란?

https://ko.wikipedia.org/wiki/이분_그래프

모든 정점을 두가지 색으로 칠하되, 모든 변이 두가지 색의 정점을 포함하도록 하는 그래프
위의 이미지에서 보면 모든 간선이 빨강, 초록 정점을 가지고 있다.

즉, 그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어 있는 그래프 
< 참고 > https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html 

2. 백준 제출 풀이(DFS - 반복)

import sys

K = int(sys.stdin.readline())

# dfs 반복문으로 구현
def dfs(g, n) : # n 시작 정점
    stack = []
    visited[n] = 1
    stack.extend(g[n]) # n과 연결되 모든 정점 추가
    
    while stack :
        par, cur = stack.pop()
        if visited[cur] == 0 :
            visited[cur] = 3 - visited[par] # 1 아니면 2 로 저장
            stack.extend(g[cur]) # cur과 연결되 모든 정점 추가
        elif visited[cur] == visited[par] :
            return False
    return True

for _ in range(K) :
    V, E = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(V)]
    # 빨강색 = 1, 파란색 = 2
    visited = [0] * V
    flag = True
    for _ in range(E) :
        x, y = map(int, sys.stdin.readline().split())
        graph[x-1].append((x-1, y-1))
        graph[y-1].append((y-1, x-1))
    
    # 비연결 그래프일 경우도 존재하므로
    # 모든 정점을 탐색할 수 있도록!
    for i in range(V) :
        if visited[i] == 0 :
            if dfs(graph, i) == False:
                flag = False
                break
    if flag :
        print("YES")
    else :
        print("NO")

DFS로 구현하는데 처음에는 stack에 그때그때마다 쌓는 방식으로 구현하여 반복횟수도 많고 이 문제를 해결하기 위한 조건문 하나를 
추가하니까 바로 시간초과가 발생했다. 그래서 반복횟수를 좀 더 줄일 수 있는 방법을 찾아보다가
< DFS 구현 참고 블로그 > https://juhee-maeng.tistory.com/entry/Python-깊이-우선-탐색DFS-구현하기
위 블로그에서 구현한 방식을 보고 아래의 코드와 같이 내가 처음에 구현한 방식을 보니 while 반복문 속 for 반복문을 사용했다.
이렇게 사용하니 반복횟수 자체도 차이가 나고 그 안에 있는 조건문 실행 횟수도 차이가 난다는 것을 알 수 있었다.
비록 이 풀이가 속도가 빠른 풀이라고 할 수는 없지만 다른 인터넷에서 보던 글과 다르게 반복으로 풀어냈다는 것에 우선 뿌듯하다.

# 시간 초과 코드
    while stack :
        flag = False
        cur = stack[-1] 
        for i in g[cur] : 
            if visited[i] == 0 :
                stack.append(i)
                visited[i] = 3 - visited[cur]
                flag = True
                break
            else :
                if visited[i] == visited[cur] :
                    return False
        if not flag : # 더이상 탐색할 노드가 없으면
            stack.pop()

그리고 이 문제에서 중요한 점은 비연결 그래프일 가능성이 존재한다는 것이다.

예시 입력
1
5 4
1 2
3 4
3 5
4 5

출력
NO

비연결 그래프일 경우 연결된 것끼리 이분 그래프가 모두 성립해야지만 YES를 출력할 수 있다.

---

2. 21606번 - 아침 산책

1. 73점 코드🥲

import sys

N = int(sys.stdin.readline())
# 1 = 실내, 0 = 실외
A = sys.stdin.readline()
count = 0

walk = [[] for _ in range(N)]
for _ in range(N-1) :
    u, v = map(int, sys.stdin.readline().split())
    walk[u-1].append(v-1)
    walk[v-1].append(u-1)

def dfs(start) :
    global count
    visited = [0] * N
    
    visited[start] = 1
    stack = []
    stack.extend(walk[start])
    
    while stack :
        cur = stack.pop()
        if visited[cur] == 0 :
            visited[cur] = 1
            if A[cur] == "0" : # 실외일 경우만  후에 더 탐색학 노드 추가
                stack.extend(walk[cur])
            else : # 실내일 경우 하나의 산책로 완성
                count += 1

for i in range(N) :
    if A[i] == "1" :
        dfs(i)
print(count)

직접 생각해서 풀긴 했지만 점수는... 
일단 간단하게 생각하면서 푼 문제라 데이터가 커지면서 시간초과 오류로 만점을 받지 못했다.

2. 200점 코드💯

import sys

count = 0
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().strip()))

walk = [[] for _ in range(N)]

for _ in range(N-1) :
    u, v = map(int, sys.stdin.readline().split())
    walk[u-1].append(v-1)
    walk[v-1].append(u-1)
    # 연결된 정점(a, b)이 모두 실내이면
    # a -> b or b -> a 2가지 경로가 만들어진다.
    if A[u-1] == 1 and A[v-1] == 1 :
        count += 2

def dfs(v) : # v : 시작 정점
    cnt = 0
    visited[v] = 1
    stack = []
    stack.extend(walk[v])
    while stack :
        cur = stack.pop()
        if A[cur] == 1 : # 현재 노드가 실내라면 
            cnt += 1
        # 실외 노드이고 방문한 적이 없으면 계속해서 탐색
        elif visited[cur] == 0 and A[cur] == 0 :
            visited[cur] = 1
            stack.extend(walk[cur])
    return cnt

visited = [0] * N
for i in range(N) :
    if  visited[i] == 0 and A[i] == 0 : # 실외 노드라면
        # 가능한 경우의 실외노드들의 경로에 연결되어 있는 실내 노드의 개수 c
        c = dfs(i)
        # 무조건 실내에서 시작하여 실내로 끝나야 하므로
        # 현재 연결된 실내 노드 2개를 선택할 수 있는 경우의 수 만큼 경로 생성 가능
        count += c*(c-1)

print(count)

솔직히 도저히 어떻게 해야할지 감이 안잡혀서 블로그를 참고했다.
< 참고 블로그 > WOONY's growth insight

처음에 무조건 실내를 기준으로 생각했는데 여기서는 오히려 실외를 기준으로 풀었다.
내 코드를 보면 나는 무조건 다 돌아보며 count를 증가시키면서 구하는 방법을 사용해서 따지고 보면 완전탐색하는 꼴이다.

그러나 참고한 코드를 보면
1. 이미 연결된 간선이 실내끼리 연결하면 바로 2개 추가
2. 실외를 기준으로 dfs 탐색 : 실외 노드끼리 연결된 하나의 경로 생성
3. 2번 과정에서 만들어진 하나의 경로에 연결되어 있는 실내 노드의 개수를 이용하여 가능한 경로의 수 계산
4. 아직 방문하지 않은 실외 노드가 존재하면 2,3번 과정 반복

이와 같은 과정으로 코드를 구현했다.
그래서 최대한 내 코드를 이용하는 선에서 위와 같이 알고리즘을 적용해 보았다. 

---

3. 14888번 - 연산자 끼워넣기

import sys

N = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
plus, minus, mul, div = map(int, sys.stdin.readline().split())

max_result = -sys.maxsize
min_result = sys.maxsize

def dfs(count, total, plus, minus, mul, div) :
    global max_result, min_result
    
    if count == N :
        max_result = max(max_result, total)
        min_result = min(min_result, total)
        return
    if plus > 0 :
        dfs(count+1, total + nums[count], plus-1, minus, mul, div)
    if minus > 0 :
        dfs(count+1, total - nums[count], plus, minus-1, mul, div)
    if mul > 0 :
        dfs(count+1, total * nums[count], plus, minus, mul-1, div)
    if div > 0 :
        if total < 0 :
            tmp = (-total) // nums[count]
            tmp = -tmp
        else :
            tmp = total // nums[count]
        dfs(count+1, tmp, plus, minus, mul, div-1)

dfs(1, nums[0], plus, minus, mul, div)        

print(max_result)
print(min_result)

이전에 완전 탐색을 연습하면서 풀었던 문제라서 기억이 났다. 

전에 / 와 // 의 차이를 공부했었는데 순간 기억이 나직 않아서 나눗셈 과정을 풀어서 코딩을 해버렸다...
다시 한번 기억해둬야 겠다.

https://soo-note.tistory.com/41

2. 그래프 문제 풀이(BFS)

1. 18352번 - 특정 거리의 도시 찾기

import sys
from collections import deque

N, M, K, X = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N)]

for _ in range(M) :
    a, b = map(int, sys.stdin.readline().split())
    graph[a-1].append(b-1)

result = []

def bfs(x):
    visited = [sys.maxsize] * N
    queue = deque()
    
    visited[x] = 0
    queue.append(x)
    
    while queue :
        cur = queue.popleft()
        for i in graph[cur] :
            if visited[i] == sys.maxsize :
                visited[i] = visited[cur] + 1
                queue.append(i)
                if visited[i] == K :
                    result.append(i+1)

bfs(X-1)
if len(result) == 0 :
    print(-1)
else :
    result.sort() # 결과를 오름차순으로 출력!!
    for i in result :
        print(i)

문제 조건 잘 알아봐야 한다... 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력