태야

<내 코드>

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. 탐색하며 더한 가중치 값들 중 최댓값을 출력하면, 트리의 지름이 된다.

<내 코드>

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': ('.', '.')
}

<내 코드>

T = int(input())
for _ in range(T):
    case = input()
    cnt = 0
    for i in case:
        if i == '(':
            cnt += 1
        elif i == ')':
            cnt -= 1

        if cnt < 0:
            print("NO")
            break
    if cnt == 0:
        print("YES")
    elif cnt > 0:
        print("NO")

<내 코드>

N = int(input())
nums = list(map(int, input().split()))
nums.sort()

sum_num = 0

for i in range(N):
    if sum_num + 1 >= nums[i]:
        sum_num += nums[i]
    else:
        break
print(sum_num + 1)

1. 입력 값 오름차순 정렬

2. 다음에 등장하는 숫자가 (누적합 + 1) 이하라면 누적합 + 1까지의 숫자들은 기존의 숫자들의 조합으로 모두 표현 가능하다.

3. 하지만, 다음에 등장하는 숫자가 (누적합 + 2) 이상이라면 기존의 숫자들의 조합으로 (누적합 + 1) 표현이 불가능하므로 (누적합 + 1)을 출력해준다. 

생각지도 못한 문제 해결 방법이었다..그리디 문제를 조금 더 다양하게 풀어봐야겠다.

<내 코드>

from collections import deque


def bfs(x1, y1, x_end, y_end):

    queue.append([x1, y1])
    done[x1][y1] = 1

    while queue:

        x, y = queue.popleft()

        if (x, y) == (x_end, y_end):
            return (done[x][y] - 1)

        for i in range(8):
            nx = x + move[i][0]
            ny = y + move[i][1]

            if(0 <= nx < n) and (0 <= ny < n) and done[nx][ny] == 0:

                queue.append([nx, ny])
                done[nx][ny] = done[x][y] + 1


case = int(input())

move = [[1, 2], [2, 1], [-1, 2], [-2, 1],
        [1, -2], [2, -1], [-1, -2], [-2, -1]]

for _ in range(case):
    n = int(input())
    start_x, start_y = map(int, input().split())
    end_x, end_y = map(int, input().split())

    done = [[0]*n for _ in range(n)]
    queue = deque()

    # 예외처리
    if start_x == end_x and start_y == end_y:
        print(0)
        continue

    ans = bfs(start_x, start_y, end_x, end_y)
    print(ans)

처음에는 min()을 이용해 모든 경우에 대해 최소를 찾으려고 잘 못 생각했다. 역시나 구현이 제대로 안됐다. 

n x n 크기 배열을 만들어 각 지나온 좌표값에 이전 좌표의 값에 +1을 계속해 더해 원하는 지점에 도달했을 때 그때의 값을 출력하면 문제의 정답이 된다. 즉, 현재 지점에서 8방향으로 갈 수 있는 지점을 현재 지점의 값에 +1을 해나가면 되는 것이다.

<내 코드>

- DFS

import sys
sys.setrecursionlimit(10000)


def dfs(x, y, type):

    done.append((x, y))

    # 4방향 확인
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if(0 <= nx < N) and (0 <= ny < N) and ((nx, ny) not in done):
            # 정상인
            if type == 0 and colors[nx][ny] == colors[x][y]:
                dfs(nx, ny, 0)
            # 적록색맹
            elif type == 1 and colors[nx][ny] == colors[x][y]:
                dfs(nx, ny, 1)


N = int(input())
colors = [list(input()) for _ in range(N)]

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

# 정상인인 경우
done = []
cnt_1 = 0

for i in range(N):
    for j in range(N):
        if (i, j) not in done:
            dfs(i, j, 0)
            cnt_1 += 1


# 적록색맹인 경우
for i in range(N):
    for j in range(N):
        if colors[i][j] == 'G':
            colors[i][j] = 'R'

done = []
cnt_2 = 0
for i in range(N):
    for j in range(N):
        if (i, j) not in done:
            dfs(i, j, 1)
            cnt_2 += 1

print(cnt_1, cnt_2)

DFS로 풀 때 런타임 에러 방지하기 위해 sys.setrecursionlimit(10000) 설정해준다. 그리고 type 값에 따라 정상인과 색약의 상태를 구분해 탐색한다. 시간을 조금 더 줄여보는 방법을 생각해봐야겠다.

- BFS

from collections import deque


def bfs(x, y):
    queue.append((x, y))
    done.append((x, y))
    
    while queue:
        curr = queue.popleft()

        for i in range(4):
            nx = curr[0] + dx[i]
            ny = curr[1] + dy[i]

            if (0 <= nx < N) and (0 <= ny < N) and ((nx, ny) not in done):
                if colors[nx][ny] == colors[curr[0]][curr[1]]:
                    queue.append((nx, ny))
                    done.append((nx, ny))


N = int(input())
colors = [list(input()) for _ in range(N)]

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

# 정상인인 경우
queue = deque()
done = []
cnt_1 = 0

for i in range(N):
    for j in range(N):
        if (i, j) not in done:
            bfs(i, j)
            cnt_1 += 1


# 적록색맹인 경우
for i in range(N):
    for j in range(N):
        if colors[i][j] == 'G':
            colors[i][j] = 'R'

queue = deque()
done = []
cnt_2 = 0
for i in range(N):
    for j in range(N):
        if (i, j) not in done:
            bfs(i, j)
            cnt_2 += 1

print(cnt_1, cnt_2)

<내 코드>

import sys
sys.setrecursionlimit(10000) 


def dfs(x, y, cnt):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    now = (x, y)

    global ans
    ans = max(ans, cnt)

    for i in range(4):
        nx = now[0] + dx[i]
        ny = now[1] + dy[i]

        if(0 <= nx < R) and (0 <= ny < C):
            if(done[strings[nx][ny]] == 0):
                done[strings[nx][ny]] = 1
                # print(done)
                dfs(nx, ny, cnt+1)
                done[strings[nx][ny]] = 0  #백트래킹


R, C = map(int, input().split())
strings = [list(map(lambda x: ord(x)-65, input())) for _ in range(R)] # 아스키 코드로 바꿔줌
done = [0]*26   # 알파벳 26개만큼 배열설정
done[strings[0][0]] = 1

ans = 1

dfs(0, 0, ans)
print(ans)

계속해서 시간 초과가 나서 실패하고, 이 코드로 겨우 통과했다. 알고리즘은 계속해서 맞았지만 재귀를 활용하다 보니 시간 초과가 많이 났다. 백트래킹의 기본 동작원리를 이해할 수 있는 문제였다.

<내 코드>

T = int(input())
for _ in range(T):
    strings = list(input())

    if strings[0] == 'O':
        strings[0] = 1
    else:
        strings[0] = 0

    for i in range(1, len(strings)):
        if strings[i-1] != 'O' and strings[i] == 'O':
            strings[i] = strings[i-1] + 1
        else:
            strings[i] = 0
    print(sum(strings))