[04.02/week03]TIL

오늘 한줄 요약

쌓여가는 REVIEW QUEUE, 복잡해진 내머리...

오늘 공부한 것

• DFS (21606, 14888)
• BFS (7569, 3055)
• 위상 정렬(2637)

새로 배우게 된 것

DFS

• 기본 코드

def dfs(graph, start, visited):
	vistied[start] = True
    print(start, end=' ')
    for i in graph[start]:
    	if not visited[i]:
        	dfs(graph, i, visited)

21606

• 틀린 이유
  일단 실내 - 실외 - 실내 Case 이외 실외가 여러개인 Case와, 실내 - 실내 Case를 생각하지 못했다.

# 1. 입력받기
# 2. 그래프 생성 -> 노드와 실내,실외 정보 담기
# 3. DFS 탐색 실행 -> 실내 - 실내 면 종료, 실내 - 실외는 실내 만날때 까지 진행

import sys
input = sys.stdin.readline

N = int(input())

status = [0] +list(map(int,list(input().rstrip()))) # 1이면 실내, 0이면 실외

graph = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)
route = 0

for _ in range(N - 1):
  u, v = map(int, input().split())
  graph[u].append(v)
  graph[v].append(u)
  # 두 정점 모두 실내라면 경로의 수 2 증가
  if status[u] == 1 and status[v] == 1:
    route += 2


def DFS(start):
  visited[start] = True
  inside_count = 0 # 현재 노드와 인접한 실내 노드 개수 저장할 변수
  for v in graph[start]:
    if status[v] == 1:
      inside_count += 1 # 실내 노드 개수 증가

    elif not visited[v] and status[i] == 0:
      inside_count += DFS(v) # 인접 노드가 실외라면 그 노드부터 탐색하여 실내 노드 개수 증가
  return inside_count

for i in range(1, N + 1):
  if status[i] == 0 and not visited[i]:
    result = DFS(i)
    route += result * (result - 1)


print(route)

14888

• 틀린이유
  DFS로 무엇을 찾아야 하나 를 명확히 하지 못해 틀렸다.
  처음에 숫자 리스트를 노드로, 연산자를 간선으로 생각했으나 그런 디테일이 부족했다. 한 자리에서 다른 자리로 이동할때 사칙연산이니 4가지의 경로가 있었던 것이고, 이때 연산자가 존재하는 경우에만 그 간선으로 갈 수 있던 것

from itertools import permutations
import sys
input = sys.stdin.readline

def dfs(n, sum, add, sub, mul, div):
  global mn, mx
  
  # 마지막 수에 도달 했을 때 종료 조건 발동
  if n == N :
    mn = min(mn, sum)
    mx = max(mx, sum)
    return
  
  # 연산자 개수 있다면 하부 호출
  if add > 0:
    dfs(n+1, sum + num_list[n], add -1, sub, mul, div)
  if sub > 0:
    dfs(n+1, sum - num_list[n], add, sub - 1, mul, div)
  if mul > 0:
    dfs(n+1, sum * num_list[n], add, sub, mul - 1, div)
  if div > 0:
    dfs(n+1, int(sum / num_list[n]), add, sub, mul, div - 1)


N = int(input()) # 숫자 개수
num_list = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())

mn, mx = int(1e9), int(-1e9)

dfs(1, num_list[0], add, sub, mul, div)
print(mx, mn, end='\n')

BFS

• 기본 코드

from collection import deque

def bfs(graph, start, visited):
	queue = deque([start])
    visited[start] = True
    while queue:
    	node = queue.popleft()
        for i in graph[node]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True

7569

• 틀린이유
  일단 3차원 그래프를 입력받지도 못했고, 이를 BFS 돌리지도 못했다.
  다만, 6방향을 dx,dy,dh 를 활용해서 돌아야겠다는 생각을 했다는 것에 위안을 삼자.

from collections import deque
import sys
input = sys.stdin.readline

def bfs(graph, H, N, M):
    # 방향 벡터 (상, 하, 좌, 우, 위, 아래)
    dh = [0, 0, 0, 0, 1, -1]
    dy = [-1, 1, 0, 0, 0, 0]
    dx = [0, 0, -1, 1, 0, 0]

    queue = deque()

    # 익은 토마토 위치 큐에 추가
    for h in range(H):
        for y in range(N):
            for x in range(M):
                if graph[h][y][x] == 1:
                    queue.append((h, y, x))

    while queue:
        h, y, x = queue.popleft()

        for i in range(6):
            nh, ny, nx = h + dh[i], y + dy[i], x + dx[i]

            if 0 <= nh < H and 0 <= ny < N and 0 <= nx < M:
                if graph[nh][ny][nx] == 0:
                    graph[nh][ny][nx] = graph[h][y][x] + 1
                    queue.append((nh, ny, nx))

    return graph


# 입력
M, N, H = map(int, input().split())  # 가로, 세로, 높이
graph = []

for _ in range(H):
    floor = []
    for _ in range(N):
        floor.append(list(map(int, input().split())))
    graph.append(floor)

# BFS 실행
graph = bfs(graph, H, N, M)

# 결과 확인
max_day = 0
for h in range(H):
    for y in range(N):
        for x in range(M):
            if graph[h][y][x] == 0:
                print(-1)
                sys.exit(0)
            max_day = max(max_day, graph[h][y][x])

print(max_day - 1)

3055

• 틀린이유
  일단 물과 고슴도치 두 가지를 BFS 를 한다는 것 자체를 떠올리지 못했다.
  시작조차 못했음

import sys
from collections import deque
input = sys.stdin.readline

R, C = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(R)]
visited = [[-1] * C for _ in range(R)]

water_q = deque()
hedgehog_q = deque()

for y in range(R):
    for x in range(C):
        if graph[y][x] == '*':
            water_q.append((y, x))
        elif graph[y][x] == 'S':
            hedgehog_q.append((y, x))
            visited[y][x] = 0

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

while hedgehog_q:
    # 먼저 물 퍼뜨리기
    for _ in range(len(water_q)):
        y, x = water_q.popleft()
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if 0 <= ny < R and 0 <= nx < C:
                if graph[ny][nx] == '.':
                    graph[ny][nx] = '*'  # 물로 확산
                    water_q.append((ny, nx))

    # 그다음 고슴도치 이동
    for _ in range(len(hedgehog_q)):
        y, x = hedgehog_q.popleft()
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if 0 <= ny < R and 0 <= nx < C:
                if graph[ny][nx] == 'D':  # 비버 굴 도착
                    print(visited[y][x] + 1)
                    sys.exit(0)
                if graph[ny][nx] == '.' and visited[ny][nx] == -1:
                    visited[ny][nx] = visited[y][x] + 1
                    hedgehog_q.append((ny, nx))

# 여기까지 왔다면 도달 실패
print("KAKTUS")

큐를 두개쓰는 버전으로 공부를 했는데, 물을 먼저 넣고, 고슴도치를 나중에 넣어서 자연스레 물먼저 BFS를 돌리는 방법도 있다고 함.

위상정렬

• 기본 코드

from collections import deque

indegree = [0] * (V + 1) # 차수 초기화

for _ in range(E):
	graph[u].append(V)
    indegree[v] += 1 # 진입차수!

def topology_sort():
	result = []
	queue = deque()
    for i in range(1, V + 1):
    	if indegree[i] == 0:
        	queue.append(i)
    while queue:
    	now = queue.popleft()
        result.append(now)
        for next in graph[now]:
        	indegree[next] -= 1 # 간선 제거
            if indegree[next] == 0:
            	queue.append(next)

2637

• 틀린 이유
  일단 기본부품과 중간 부품의 차이 정립이 안되어있던 상황이었음.

• 기본 부품:

  다른 부품을 만들 때만 사용되고, 어떤 부품으로도부터 만들어지지 않는 부품

  → 즉, 진입차수(degree)가 0인 부품들
  

• 중간 부품 & 완제품:

  다른 부품을 이용해서 만들어지는 부품

  → 즉, 진입차수가 1 이상
  

import sys
from collections import deque

input = sys.stdin.readline
n = int(input())
connect = [[] for _ in range(n + 1)]  # 연결 정보
needs = [[0] * (n + 1) for _ in range(n + 1)]  # 각 제품을 만들때 필요한 부품
q = deque()  # 위상 정렬
degree = [0] * (n + 1)  # 진입 차수
for _ in range(int(input())):
    a, b, c = map(int, input().split())
    connect[b].append((a, c))
    degree[a] += 1

for i in range(1, n + 1):
    # 진입 차수가 0인걸 넣어준다.
    if degree[i] == 0: # 기본 부품부터 삽입
        q.append(i)
# 위상 정렬 시작
while q:
    now = q.popleft()
    # 현 제품의 다음 단계 번호, 현 제품이 얼마나 필요한지
    for next, next_need in connect[now]:
        # 만약 현 제품이 기본 부품이면
        if needs[now].count(0) == n + 1:
            needs[next][now] += next_need
        # 현 제품이 중간 부품이면
        else:
            for i in range(1, n + 1):
                needs[next][i] += needs[now][i] * next_need
        # 차수 -1
        degree[next] -= 1
        if degree[next] == 0:
            # 차수 0이면 큐에 넣음
            q.append(next)
for x in enumerate(needs[n]):
    if x[1] > 0:
        print(*x)
print(needs)

공부하다가 아쉬운 점

문제를 조금 끝까지 물고 늘어졌어야 하는데
시간이 없다보니 1시간 반이상 잡는다면 답을 보았다.
물론 답을 보고 공부를 했지만, 뭔기 이 문제에 진 느낌...