[python code review] 14주차 (컵라면, 트리의 지름, 파이프 옮기기1)

https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

[dfs]

트리의 지름을 구하는 공식을 모르면 풀 수 없는 문제 

* 트리의 지름 구하기 : 아무 노드나 하나를 정해서(root) 가장 먼거리에 있는 노드(far_node)를 구하고, 그 노드와 가장 먼 노드의 거리를 구하면 트리의 지름이다. 

* 귀류법을 사용하면 명제를 증명할 수 있다고 한다.

import sys
sys.setrecursionlimit(10**5)

def dfs(node, total):
    global answer, far_node

    visited[node] = True

    for cost, next_node in graph[node]:
        if not visited[next_node]:
            dfs(next_node, total+cost)
    else:
    	# 리프 노드인 경우 
        if answer < total:
            answer = total
            far_node = node


n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    graph[a].append((c, b))
    graph[b].append((c, a))
visited = [False for _ in range(n+1)]
answer = 0; far_node = 0
dfs(1, 0)
visited = [False for _ in range(n+1)]
dfs(far_node, 0)
print(answer)

 

https://www.acmicpc.net/problem/1781

1781번: 컵라면

[heapq]

7일 차때 데드라인 7일 안에서 고르기 

6일 차때 데드라인 6~7일 안에서 고르기 

5일 차때 데드라인 5~7일 안에서 고르기 

4일 차때 데드라인 4~7일 안에서 고르기 

3일 차때 데드라인 3~7일 안에서 고르기 

...

1일 차때 데드라인 1일 안에서 고르기 

 

7일차부터 1일차에 거꾸로 접근하면서 7일차에는 데드라인이 7일인 경우만 접근 가능하기 때문에

데드라인 7일에 해당하는 라면들을 heap에 최대힙으로 넣어주었다.

6일차에도 마찬가지 로직으로 데드라인이 6일인 경우의 라면값들을 heap에 넣어준다.  

import heapq

n = int(input())
graph = [[] for _ in range(n+1)]
heap = []
for _ in range(n):
    d, l = map(int, input().split())
    graph[d].append(l)

answer = 0
for i in range(n, 0, -1):
    for l in graph[i]:
        heapq.heappush(heap, -l)
    if heap:
        answer += heapq.heappop(heap)
print(-answer)

 

https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

[dfs]

이동할 때 45도 회전만 가능하고 대각선으로 이동할 경우 양 사이드 위치에 벽이 없어야 한다는 것이 가장 핵심인 문제이다. 일반적인 moves 배열 만들어서 dfs로 만들었다가 틀렸다. 이 문제의 경우, 이동 가능한 경우의 분기를 나누고 조건 처리 후 dfs 탐색을 진행해야 한다. 

이동 가능한 경우

1) 세로 대각선 -> 세로 

2) 가로 대각선 -> 가로

3) 가로 세로 대각선 -> 대각선 

def dfs(x, y, shape):
    global moves, answer
    if (x, y) == (n-1, n-1):
        answer += 1
        return

    # 가로, 세로, 대각선 -> 대각선
    if shape == 0 or shape == 1 or shape == 2:
        if x+1 < n and y+1 < n:
            if not board[x+1][y] and not board[x][y+1] and not board[x+1][y+1]:
                dfs(x+1, y+1, 2)
    # 가로, 대각선 -> 가로
    if shape == 0 or shape == 2:
        if y + 1 < n and not board[x][y+1]:
            dfs(x, y+1, 0)
    # 세로, 대각선 -> 세로
    if shape == 1 or shape == 2:
        if x + 1 < n and not board[x+1][y]:
            dfs(x+1, y, 1)

answer = 0
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
moves = [(0,1),(1,0),(1,1)]
dfs(0, 1, 0)
print(answer)