태야

<내 코드>

T = int(input())

for _ in range(T):
    N, M = map(int, input().split())
    for _ in range(M):
        a, b = map(int, input().split())
    print(N-1)

일단 문제에서 모든 곳이 연결된 그래프이기 때문에, 최소 비행기 수는 (나라 수 - 1)이다. 왜냐하면 모든 나라를 여행하는 것이라 시작점을 어디든지 될 수 있다. 즉, 한중일 세 나라가 있다면 한국 - 일본, 한국 - 중국 이런식으로 시작점을 맘대로 정할 수 있기 때문이다.

<내 코드>

import sys
sys.setrecursionlimit(100000)


def dfs(start, tree, weight, ck):
    # ck로 루트1번에서 시작한 건지, 최장길이 노드를 루트로 한건지 판단
    if ck == 1:
        weight[1] = 0  # 루트 1번 노드 가중치 0으로 설정

    for node, w in tree[start]:
        if(weight[node] == 0):
            weight[node] = weight[start] + w  # 현재 가중치 + 다음 노드와 가중치
            dfs(node, tree, weight, ck)


n = int(sys.stdin.readline())
tree = [[] for _ in range(n+1)]
# 입력 값 tree 생성
for _ in range(n-1):
    p_node, c_node, w = map(int, sys.stdin.readline().split())
    tree[p_node].append((c_node, w))
    tree[c_node].append((p_node, w))

weight1 = [0 for _ in range(n+1)]  # 루트1로부터 길이를 저장
dfs(1, tree, weight1, 1)  # 루트 1 시작점으로 해 가장 먼 노드를 찾음


# 찾은 가장 먼 노드를 시작 노드로 탐색
# 최장경로 노드에서 다시 DFS를 통해 트리지름구하기
start_node = weight1.index(max(weight1))
weight2 = [0 for _ in range(n+1)]

dfs(start_node, tree, weight2, 2)

print(max(weight2))

같은 코드로 python3, pypy3로 제출했을 때 시간 차이가 5000ms 정도 차이가 났다...

확실히 DFS는 시간이 많이 걸리는 것 같다. 파이썬은 테스트에서 되도록이면 BFS를 이용하는 게 좋지 않을까 생각한다.

알고리즘 이해

: 일단 트리의 지름을 구하려면 가장 끝 노드끼리 거리가 될거다. 거기서도 가장 큰 가중치(거리)를 가지는 것이 최종 지름이 된다.

1. 루트 1번을 시작으로 해서 가장 긴(먼 거리)에 있는 즉, 가중치가 큰  끝 노드를 DFS 탐색으로 찾는다.

2. 찾은 끝 노드를 다시 루트노드로 설정해 DFS 탐색을 한다.

3. 탐색하며 더한 가중치 값들 중 최댓값을 출력하면, 트리의 지름이 된다.

<내 코드>

import sys
sys.setrecursionlimit(100000) #런타임 에러 방지

n = int(input())
tree = [[] for _ in range(n+1)]

# 양방향으로 노드를 연결하고
for _ in range(n-1):  # 노드의 수 - 1 (간선)
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

# 각 노드의 부모 노드 값 저장용
parents = [0 for _ in range(n+1)]
parents[1] = 1


def dfs(curr, tree, parents):
    # print(parents)
    for node in tree[curr]:
        if parents[node] == 0:
            parents[node] = curr  # 해당 자식 노드에 부모노드(curr) 값 넣음
            dfs(node, tree, parents)  # 자식 노드가 서브 트리 루트로서 탐색


dfs(1, tree, parents)

print(*parents[2:])

<내 코드>

def preorder(node):
    if node == '.':
        return
    print(node, end="")
    preorder(tree[node][0])  # tree[key][value], 왼쪽 자식 노드
    preorder(tree[node][1])  # 오른쪽 자식 노드


def inorder(node):
    if node == '.':
        return
    inorder(tree[node][0])  # 왼쪽 자식 노드
    print(node, end="")
    inorder(tree[node][1])  # 오른쪽 자식 노드


def postorder(node):
    if node == '.':
        return
    postorder(tree[node][0])  # 왼쪽 자식 노드
    postorder(tree[node][1])  # 오른쪽 자식 노드
    print(node, end="")


n = int(input())
tree = {}

# tree 생성
for _ in range(n):
    root, left, right = input().split()
    tree[root] = (left, right)

#print(tree)
preorder('A')
print()
inorder('A')
print()
postorder('A')

딕셔너리를 이용해 트리를 만들어준다. 그다음 각 순회 방식에 맞게 재귀를 이용해 함수를 작성해준다.

# tree
{
  'A': ('B', 'C'), 
  'B': ('D', '.'), 
  'C': ('E', 'F'), 
  'E': ('.', '.'), 
  'F': ('.', 'G'), 
  'D': ('.', '.'), 
  'G': ('.', '.')
}

<내 코드>

N, M = map(int, input().split())
nums = list(map(int, input().split()))
sum = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            if ((nums[i] + nums[j] + nums[k]) > M):
                continue
            else:
                sum = max(sum, nums[i] + nums[j] + nums[k])
print(sum)

from itertools import combinations

N, M = map(int, input().split())
nums = list(map(int, input().split()))
result = 0

for cards in combinations(nums, 3):
    sum_num = sum(cards)

    if sum_num <= M and sum_num > result:
        result = sum_num

print(result)

파이썬에서 제공하는 순열 조합을 구하는 모듈인 combinations을 이용해 모든 경우를 구한다.

combinations(리스트, 몇 개씩 조합할지) 정해주면 된다.

<내 코드>

N = int(input())
nums = list(map(int, input().split()))
B, C = map(int, input().split())
result = 0

nums = [nums[i]-B for i in range(N)]
result += N

for n in nums:
    if n > 0:
        result += (n // C)
        if n % C != 0:
            result += 1


print(result)

<내 코드>

import collections

# 북, 동, 남, 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


def change(d):
    if d == 0:  # 북 -> 서
        return 3
    elif d == 1:  # 동 -> 북
        return 0
    elif d == 2:  # 남 -> 동
        return 1
    elif d == 3:  # 서 -> 동
        return 2


def search(x, y, d):
    cnt = 1
    q = collections.deque([[x, y, d]])
    route[x][y] = 2

    while q:
        x, y, d = q.popleft()
        nd = d

        for i in range(4):
            # 왼쪽 영역 탐색
            nd = change(nd)
            nx = x + dx[nd]
            ny = y + dy[nd]

            # a
            if 0 <= nx < N and 0 <= ny < M and route[nx][ny] == 0:
                cnt += 1
                route[nx][ny] = 2
                q.append([nx, ny, nd])
                break
            # c
            elif i == 3:

                if d == 0:
                    x += 1
                elif d == 1:
                    y -= 1
                elif d == 2:
                    x -= 1
                elif d == 3:
                    y += 1
                q.append([x, y, d])
                # d
                if route[x][y] == 1:
                    return cnt


N, M = map(int, input().split())
r, c, d = map(int, input().split())

route = [list(map(int, input().split())) for _ in range(N)]
print(search(r, c, d))

• 방향을 북, 동, 남, 서 방향으로 바꿔줘야 한다

• 벽인지, 빈칸인지를 잘 구별해주어야 한다

• 후진을 할 방향을 잘 선택해주면 된다

<내 코드>

import copy

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

answer = 0

def bfs():
    global answer
    v = copy.deepcopy(virus)  # 원본 유지한채 복사(바이러스 좌표값)
    tmp = [[0]*M for _ in range(N)]
    # 지도 복사
    for i in range(N):
        for j in range(M):
            tmp[i][j] = maps[i][j]

    # 4방향 탐색 후 바이러스 감염
    while len(v) != 0:
        vir = v.pop()
        vir_x = vir[0]
        vir_y = vir[1]

        for k in range(4):
            nx = vir_x + dx[k]
            ny = vir_y + dy[k]
            if 0 <= nx < N and 0 <= ny < M:
                if tmp[nx][ny] == 0:
                    tmp[nx][ny] = 2
                    v.append([nx, ny])
    # 0(안전구역) 갯수 파악
    result = 0
    for i in tmp:
        for j in i:
            if j == 0:
                result += 1

    answer = max(result, answer)

# 벽 3개를 세우는 모든 경우의 수
def wall(cnt):
    if cnt == 3:
        bfs()
        return

    for i in range(N):
        for j in range(M):
            if maps[i][j] == 0:
                maps[i][j] = 1
                wall(cnt+1)
                maps[i][j] = 0
                
N, M = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(N)]

virus = []

# 바이러스 좌표값 저장
for i in range(N):
    for j in range(M):
        if maps[i][j] == 2:
            virus.append([i, j])
wall(0)
print(answer)

벽 3개를 세우는 방법을 알지 못해 다른 사람들의 코드를 참고했다. 여기서 입력의 크기가 크지 않기 때문에 브루트포스를 사용해 벽3개를 세우는 경우의 수를 다 구했다. 모든 경우의 수를 구하는 코드를 이해하는데 쉽지 않았다..

앞으로 자주 사용될 것 같다.