TIL-2024/04/03

백준 - 1707번 이분 그래프

import sys
from collections import deque
sys.setrecursionlimit(10**6)

input = sys.stdin.readline

# DFS로 노드를 탐색하면서 같은 그룹의 노드를 만나면 탐색을 끝내고 False를 리턴한다.
def dfs(start, flag, graph, group):
	#  해당 노드를 그룹화한다.
  flag[start] = group
	
	# 노드와 연결어있으면서 방문하지 않은 노드들을 순회하며 깊이 탐색을 수행한다.
  for e in graph[start]:
    if flag[e] == 0:
      res = dfs(e, flag, graph, -group)
      
      if not res:
        return False
        
   # 같은 그룹의 노드가 이웃하게 되는 경우 이분 그래프가 불가능하다.
    elif flag[e] == group:
      return False
  
  return True

K = int(input())

for n in range(K):
  v, edges = map(int, input().split())
  graph = [[ ] for i in range(v+1)]
  visited = [0]*(v+1)
  e_list = []
	
	# 인접 리스트 생성
  for _ in range(edges):
      x, y = map(int, input().split())
      graph[x].append(y)
      graph[y].append(x)
      e_list.append([x, y])

	# 노드들이 끊어져 있는 경우가 있기 때문에 모든 노드를 반복한다.
  for index in range(1, v + 1):
	  # 노드를 방문하지 않은 경우
    if visited[index] == 0:
		   # 깊이 탐색을 통해 이어진 노드를 순회하며 노드를 그룹화한다.
      res = dfs(index, visited, graph, 1)
      
      # 해당 노드와 연결된 노드들에서 이분 그래프를 만들 수 없으면 반복을 중단한다.
      if not res:
        break

  print('YES') if res else print('NO')
    

😩 못 푼 원인 😩

문제 이해를 제대로 못한 것 같다. 문제 그대로 이해했으면 정점을 그룹화하는 방식을 고민했을텐데 간선을 제거했을 때 완전히 두 그룹으로 분리되어야한다는 뉘앙스로 잘못 이해해서 너무 어렵게 생각한 것 같다.

백준 - 2665번 미로 만들기

import sys
import heapq

input = sys.stdin.readline

N = int(input())

maze = [ list(map(int, input()[:-1])) for _ in range(N) ]
visited = [ [ False ] * N for _ in range(N) ]

# 초기값 설정
queue = [[0, 0, 0]]

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

while queue:
  cost, x, y = heapq.heappop(queue)
  # 미로 끝에 도착한 경우 반복을 끝내고 결과를 출력한다.
  if x == N - 1 and y == N - 1:
    print(cost)
    break
	
	# 해당 칸에 대해서 상, 하, 좌, 우 칸으로 이동한다.
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    # 미로를 벗어나지 않고, 방문하지 않은 칸만 핸들링한다.
    if 0 <= nx < N and 0 <= ny < N and visited[ny][nx] == False:
      visited[ny][nx] = True
      
      # 다음 칸이 검은방인 경우 cost 값 갱신
      if maze[ny][nx] == 1:
        heapq.heappush(queue, [cost, nx, ny])
      else:
        heapq.heappush(queue, [cost + 1, nx, ny])
        
# ** 접근 방식 **
# 우선 순위 큐를 활용한 BFS를 통해 문제를 풀면된다.
# 특히 우선 순위 큐의 동작에 집중해서 어떤 방을 먼저 방문하는지 생각해볼 필요가 있다.
# 하얀방이던, 검은 방이던 방을 만났을 때 우선 순위 큐에 추가되는 부분은 같지만,
# 검은 방의 경우 cost가 늘어나기 때문에 우선 순위 큐 내부에서 순서가 뒤로 밀리게 된다.
# 그래서 같은 cost의 하얀 방을 BFS로 탐색하고, 미로 끝에 도달하지 못한 경우,
# 다음 방을 열어 탐색을 반복하게 된다.

😩 못 푼 원인 😩

BFS로 인접한 방을 방문하면서 이전 방의 횟수와 현재 방색깔을 통해서 현재 방에 도달하기까지 더 적게 문을 연 횟수로 갱신하는 방식으로 문제해결을 하고 있었다. 방은 여러 경로를 통해 올 수 있기 때문에 특정 방을 이미 지난 이후 더 적은 횟수로 다시 도착했을 때 이후 방에 대해서 또 다시 BFS를 걸어주는 방식을 찾지못했다.

백준 21606 - 아침 산책

60점짜리 내 접근법

텍스트 그대로 ‘실내에서 실내로 도착’하는 케이스를 DFS로 모든 실내 노드를 탐색하며 count하는 방식으로 구현했다. 하지만 이렇게 했을 때 결과는 부분 정답밖에 받을 수 없었고, 다른 분들의 풀이를 참고했다.

import sys

input = sys.stdin.readline

N = int(input())

A = [0] + [ int(i) for i in input()[:-1] ]

graph = [ [] for _ in range(N + 1) ]

for _ in range(N - 1):
  f, t = map(int, input().split())
  graph[f].append(t)
  graph[t].append(f)

count = 0

def dfs(count, start, isOut):
  visited[start] = True
  # 이제 막 나온 케이스
  if isOut == False and A[start] == 1:
    isOut = True
  # 실외에 있다가 실내로 들어온건지
  elif isOut == True and A[start] == 1:
    count += 1
    return count

  for e in graph[start]:
    if visited[e] == False:
      count = dfs(count, e, isOut)

  return count

for n in range(1, N + 1):
  visited = [ False ] * ( N + 1 )
  if A[n] == 1:
    res = dfs(0, n, False)
    count += res

print(count)

문제를 보고 간략하게 이해하는 것이 중요했던 것 같다.

결국 (실내) - (실내) 사이에 실외가 얼마나 있던 두 개의 실내구역만 고르면 되는 문제였다.

문제의 예시를 보면, 다음과 같이 경우의 수를 뽑아낼 수 있다.

CASE 1 - 실외를 거치는 경우

(실내) - (실외) * x - (실내)의 경우, 실외를 둘러싸는 노드 중 2개를 뽑는 방식과 동일하다.

따라서 전체 경우의 수는 N(N-1)이 나오게 된다. 문제의 예시에서는 1, 3, 4 노드 중 2개를 뽑는 경우이므로 3 * 2로 6개의 케이스가 나온다.

위 그림처럼 실외 사이에 실내가 끼어있는 형태의 경우에도 동일하다.

하지만 약간의 설계가 필요하다.

실외 노드에서 탐색을 시작하고 실내를 만나면 탐색을 종료하게 된다. 하지만 그렇게 되면 반대편 실외에 대한 탐색이 끊기는 상태가 되기 때문에 반복문을 통해서 모든 노드를 최소한 한번은 탐색하도록 해주어야한다.

CASE 2 - 실외를 거치지 않는 경우

실외가 없기 때문에 첫번째 케이스와는 다른 방법으로 횟수를 추가해주어야한다.

인접한 실내노드를 방문하는 경우에 (실내1) → (실내2), (실내2) → (실내1) 총 두번을 총 횟수에 추가해준다.

⚙️ 수정 코드 ⚙️

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(v):
  visited[v] = True
  
  in_count = 0
  for e in graph[v]:
    if  A[e] == 1:
      in_count += 1
    elif not visited[e] and A[e] == 0:
      in_count += dfs(e)

  return in_count

N = int(input())
A = [0] + [ int(i) for i in input()[:-1] ]
graph = [ [] for _ in range(N + 1) ]
visited = [ False ] * ( N + 1 )
total = 0

for _ in range(N - 1):
  f, t = map(int, input().split())
  graph[f].append(t)
  graph[t].append(f)
  if A[f] == 1 and A[t] == 1: # CASE 2
    total += 2

for n in range(1, N + 1):
  if A[n] == 0 and visited[n] == False: # CASE 1
      in_count = dfs(n)
      total += in_count * (in_count - 1)

print(total)