[코독하구만 팀] 2021.01.20(수) - 5주차 개인 결과

- 목표 -

codekodo.tistory.com/33

[코독하구만 팀] 2021.01.20(수) - 5주차 개인 목표

 

1. 위상 정렬

선행 과목이 있는 경우 선행 과목을 출력하고 이후에 연계된 과목을 출력하는 문제였다.

과목명이 처음에 주어지므로 이 과목명을 dict형으로 저장한다.

M개의 입력 값에서 선행 과목, 후행 과목이 입력되는데 선행 과목이 있는 경우 이를 count 해준다.

count가 0이면 이는 선행 과목이 없는 경우이다.

이후 BFS를 통해 과목 이수 순서를 탐색한다.

 

최종 코드는 

 

def find_path(subject_dict, count, first):
    visited = []
    while first:
        first.sort(reverse=True)
        e = first.pop()
        visited.append(e)
        for i in range(len(subject_dict[e])):
            count[subject_dict[e][i]] -= 1
            if count[subject_dict[e][i]] == 0:
                first.append(subject_dict[e][i])
    return visited

def main():
    n, m = map(int, input().split())
    subject_dict = {}
    count = {}
    first = []

    subject = list(input().split())
    for i in range(n):
        subject_dict[subject[i]] = []
        count[subject[i]] = 0

    for _ in range(m):
        i, j = input().split()
        subject_dict[i].append(j)
        count[j] += 1  
    
    for i in subject:
        if count[i] == 0:
            first.append(i)
    
    result = find_path(subject_dict, count, first)
    print(*result)

if __name__ == "__main__":
    main()

 

2. 정글의 법칙

위상 정렬로 접근하지 않고 그냥 브루트 포스의 방법을 썼다.

최종 코드는

 

def main():
    n = int(input())
    input_list = [0 for _ in range(n)]
    count = [0 for _ in range(n)]
    for i in range(n):
        a, b = map(int, input().split())
        input_list[i] = [a, b]
        count[i] = 0    # 먹고 먹히는 것을 표시하기 위한 리스트

    sum_all = n
    input_list = sorted(input_list, key = lambda x : (x[0], x[1]))
    for i in range(n):
        for j in range(i+1, n):
            if input_list[i][0] <= input_list[j][0] and input_list[i][1] <= input_list[j][1] and count[i] >= 0 and count[j] >= 0 and count[j] <= 2:
                sum_all -= 1    # 한 종류의 미생물이 먹혔으므로 -1
                count[i] = -1   # j 미생물에게 먹힌 i 미생물
                count[j] += 1   # j 미생물이 다른 미생물을 먹은 횟수

    print(sum_all)

if __name__ == "__main__":
    main()

 

3. 기름이 간당간당

출발 지점과 도착 지점을 찾고 A* 알고리즘을 적용하여 탐색한다.

최종적으로 계산된 기름 양이 입력된 기름 양보다 적은 경우 남은 기름 양을 출력하고, 그렇지 않은 경우 메세지를 출력한다.

 

최종 코드는

 

import math

def heuristics(x1, y1, x2, y2):
    return math.sqrt((x1-x2)**2 + (y1-y2)**2)

def oil_path(edge_dict, n, m, src_x, src_y, dst_x, dst_y):
    open_list = []
    close_list = []

    for i in edge_dict[(src_x,src_y)]:
        G = i[1]
        H = heuristics(i[0][0], i[0][1], dst_x, dst_y)
        F = G + H
        open_list.append([i[0], F, G, H])

    open_list = sorted(open_list, key = lambda x : -x[1])
    close_list.append(open_list.pop())

    while True:
        check_open_list = []
        check_close_list = []
        for i in open_list:
            check_open_list.append(i[0])
        for i in close_list:
            check_close_list.append(i[0])
        
        if (dst_x, dst_y) in check_close_list:
            break

        for i in range(len(close_list)):
            for j in edge_dict[close_list[i][0]]:
                if j[0] in check_close_list:
                    continue
                G = j[1] + close_list[i][2]
                if ((dst_x-1 <= j[0][0] <= dst_x+1) and (dst_y == j[0][1])) or ((dst_x == j[0][0]) and (dst_y-1 <= j[0][1] <= dst_y+1)):
                    H = 0
                else:
                    H = heuristics(j[0][0], j[0][1], dst_x, dst_y)
                F = G + H
                if j[0] in check_open_list:
                    if [j[0], F, G, H][1] < open_list[check_open_list.index(j[0])][1]:
                        open_list[check_open_list.index(j[0])] = [j[0], F, G, H]
                else:
                    open_list.append([j[0], F, G, H])

        open_list = sorted(open_list, key = lambda x : -x[1])
        close_list.append(open_list.pop())
    
    return close_list[len(close_list)-1][2]

def main():
    n, m, oil = map(int, input().split())
    map_list = [[] for _ in range(n)]
    edge_dict = {}

    src_x = 0
    src_y = 0
    dst_x = 0
    dst_y = 0

    for i in range(n):
        map_list[i] = list(input())
    
    # src와 dst가 (0, 0), (n-1, n-1)이 아닌 경우도 있으므로 좌표를 찾는다.
    for i in range(n):
        for j in range(m):
            if map_list[i][j] == "S":
                src_x = j
                src_y = i
                map_list[i][j] = 0
            elif map_list[i][j] == "E":
                dst_x = j
                dst_y = i
                map_list[i][j] = 0
    
    for i in range(n):  #행
        for j in range(m):  #열
            edge = []
            if i != 0:
                edge.append([(j, i-1), int(map_list[i-1][j])])
            if i != n-1:
                edge.append([(j, i+1), int(map_list[i+1][j])])
            if j != 0:
                edge.append([(j-1, i), int(map_list[i][j-1])])
            if j != m-1:
                edge.append([(j+1, i), int(map_list[i][j+1])])
            edge_dict[j, i] = edge

    answer = oil_path(edge_dict, n, m, src_x, src_y, dst_x, dst_y)

    if oil >= answer:
        print(oil-answer)
    else:
        print("Not enough oil!")

if __name__ == "__main__":
    main()

 

- 깃허브 -

github.com/k906506/2020_Winter_Assemble-And-selfcode

k906506/2020_Winter_Assemble-And-selfcode