code review/study

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

jmHan 2022. 5. 27. 13:49
반응형

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

 

1967번: 트리의 지름

파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연

www.acmicpc.net

[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번: 컵라면

상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라

www.acmicpc.net

[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

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의

www.acmicpc.net

[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)
반응형