Krafton_jungle 5기 17일차 TIL - 알고리즘 문제풀이

1. 2637 장난감 조립

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


# 위상정렬 후 정렬된 결과값 반환
def topological_sort():
    result = []
    queue = deque()

    for i in range(1, n+1):
        if in_degree[i] == 0:
            queue.append(i)

    while queue:
        current = queue.popleft()
        result.append(current)

        for index, value in graph[current]:
            in_degree[index] -= 1
            if in_degree[index] == 0:
                queue.append(index)

    return result


def return_result():
    for i in sorted_arr:
        cur_node = i
        for index, value in graph[cur_node]:
            result[index] += result[cur_node] * value


n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
in_degree = [0 for _ in range(n+1)]

basic_parts = set()

# 진입차수와 그래프 생성
for _ in range(m):
    vertex, edge, cost = map(int, input().split())
    graph[vertex].append((edge, cost))
    in_degree[edge] += 1

# 기본부품 구하기
for i in range(1, n+1):
    if len(graph[i]) == 0:
        basic_parts.add(i)

# 위상정렬된 배열 반환
sorted_arr = topological_sort()

result = [0] * (n+1)
result[sorted_arr[0]] = 1
return_result()

for i in range(1, n+1):
    if i in basic_parts:
        print(i, result[i])

위상 정렬을 하고 정렬된 순서를 지켜 값을 누적시켜가며 풀었다.

 

2. 3005 탈출

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

r, c = map(int, input().split())
map = [list(input().rstrip()) for _ in range(r)]

visited = [[-1] * c for _ in range(r)]

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

q = deque()

for y in range(r):
    for x in range(c):
        if map[y][x] == '*':
            q.appendleft((y, x))
        elif map[y][x] == 'S':
            q.append((y, x))
            visited[y][x] = 0

while q:
    # 최초엔 물을 차게 하고 후에는 고슴도치 이동
    y, x = q.popleft()
    cur = map[y][x]  # 현재 위치
    for i in range(4):
        ny, nx = y + dy[i], x + dx[i]
        if ny < 0 or ny >= r or nx < 0 or nx >= c:
            continue
        if visited[ny][nx] != -1:
            continue
        if map[ny][nx] == "*":
            continue
        if map[ny][nx] == "X":
            continue
        if cur == "*" and map[ny][nx] == "D":
            continue
        if cur == "S":
            if map[ny][nx] == "D":  # 고슴이가 가려는 위치가 비버네면 도착
                print(visited[y][x] + 1)
                break
            visited[ny][nx] = visited[y][x] + 1
        map[ny][nx] = cur
        q.append((ny, nx))
    else:
        continue
    break
else:
    print("KAKTUS")

탈출... 마치 뱀 문제를 푸는것같았다. 단순 구현인데도 조율해줘야 할 것이 너무 많아서 결국 답지를 봐버렸다.

 

3. 7569 토마토

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

M, N, H = map(int, input().split())
Tomatoes = [[list(map(int, input().split())) for _ in range(N)] for _ in range(H)]
visited = [[[False] * M for _ in range(N)] for _ in range(H)]
count = 0
queue = deque()

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


def bfs():
    while queue:
        z, y, x = queue.popleft()
        for i in range(6):
            nx, ny, nz = x + dx[i], y + dy[i], z + dz[i]
            if 0 <= nx < M and 0 <= ny < N and 0 <= nz < H and visited[nz][ny][nx] == 0 and Tomatoes[nz][ny][nx] != -1:
                queue.append((nz, ny, nx))
                Tomatoes[nz][ny][nx] = Tomatoes[z][y][x] + 1
                visited[nz][ny][nx] = True

for i in range(H):
    for j in range(N):
        for k in range(M):
            if Tomatoes[i][j][k] == 1 and visited[i][j][k] == 0:
                queue.append((i, j, k))
                visited[i][j][k] = True

bfs()

for i in range(H):
    for j in range(N):
        for k in range(M):
            if Tomatoes[i][j][k] == 0:
                print(-1)
                quit()
            count = max(count, Tomatoes[i][j][k])

print(count - 1)

토맛토... BFS 문제는 대체적으로 구현이 너무 빡빡한것같다.

 

4. 1432 그래프 수정

import heapq

# 위상정렬 후 정렬된 결과값 반환
def topological_sort():
    pq = []
    for i in range(1, n+1):
        # 진입차수가 없으면
        if in_degree[i] == 0:
            # 즉시 최대힙에 더하기
            heapq.heappush(pq, (-i, i))
    # 최대값부터 최대힙을 pop하며 접근할 거기 때문에 현재값을 정해준다.
    res = n
    while pq:
        current = heapq.heappop(pq)[1]
        result[current] = res
        for i in graph[current]:
            in_degree[i] -= 1
            if in_degree[i] == 0:
                heapq.heappush(pq, (-i, i))
        res -= 1

    return result

n = int(input())
in_degree = [0 for _ in range(n+1)]
graph = [[] for _ in range(n+1)]

for i in range(1, n+1):
    row = input().rstrip()
    for j in range(len(row)):
        if row[j] == "1":
            graph[int(j)+1].append(i)
            in_degree[i] += 1

result = [0] * (n+1)

sorted_arr = topological_sort()

if sum(sorted_arr) != 0:
    print(*sorted_arr[1:])
else:
    print(-1)

처음 풀어본 플레티넘 문제.

사실상 위상정렬의 특징을 알면  풀기 쉬움.

가장 큰 정점부터 역으로 추적해 가면 위상정렬의 해가 모두 다르게 나올 수 있다는 문제를 해결할 수 있다.