Algorithm175 1068. 트리 (Swift, Python) 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 2차원 배열을 만들어 각 노드에 자신의 자식 노드 리스트를 담아둔다. 예를 들어 입력이 -1 0 0 1 1 과 같은 형태로 주어지면 0은 root 노드로 설정하고 1과 2는 부모 노드가 0이므로 배열의 [0]에 [1, 2]를 담는다. 3과 4는 부모 노드가 1이므로 배열의 [1]에 [3, 4]를 담는다. 그 후 root 노드부터 dfs 탐색을 시작한다. dfs로 노드를 탐색하면서 현재 노드에 자식 노드가 하나도 없을 경우 카운트를 증가시키고 탐색을 종.. 2021. 12. 2. [LeetCode] 778. Swim in Rising Water (Swift, Python) Swim in Rising Water - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 우선수위 큐를 활용한 bfs로 해결할 수 있는 문제이다. [0][0]에서 시작해서 [n-1][n-1]로 갈 때까지의 최소 시간을 구해야 한다. 큐에 담을 때 time 값을 해당 좌표의 grid 값을 담아두는데 큐에서 값을 꺼낼 때 time 값이 가장 작은 것을 가져와야 하므로 우선순위 큐를 활용한다. 큐에 있는 값들 중 가장 작은 time을 가진 원소를 꺼내면서 res의.. 2021. 11. 30. [LeetCode] 841. Keys and Rooms (Swift, Python) Keys and Rooms - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 0번 방부터 탐색하는 dfs를 사용하면 된다. visited 배열을 만들어서 n번 방에 들어갈 수 있는지를 체크한다. 각 방에 들어갈 때마다 방에 있는 열쇠들을 for문을 통해서 아직 방문하지 않은 방의 열쇠일 경우 dfs 함수를 재귀적으로 호출해서 visited 여부를 바꿔준다. 코드 [Swift] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 .. 2021. 11. 29. 1738. 골목길 (Swift, Python) https://www.acmicpc.net/problem/1738 1738번: 골목길 첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 www.acmicpc.net 풀이 민승이네 집(1번)에서 코레스코 콘도(n번)까지 가는데 있어서 최적의 경로를 찾는 문제이다. 가는 경로에 음수가 존재하므로 다익스트라 알고리즘으로는 해결할 수 없고 벨만 포드 알고리즘을 이용해서 해결 가능하다. 기존과의 차이점은 보통 목적지까지 최단 거리를 찾는거였다면 이번 문제는 금품의 양이 최대가 되는 경로를 찾는 것이다. 하나 주의할 건 기존의 벨만 포드 알고리즘.. 2021. 11. 18. [LeetCode] 64. Minimum Path Sum (Swift, Python) Minimum Path Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 (0, 0)에서 출발하여 (m-1, n-1)까지 갈 때 grid에 적혀 있는 숫자의 합이 최솟값이 되는 경우를 찾는 문제. 간단하게 bfs를 사용해서 문제를 풀었는데 다른 사람들의 속도를 보니 dp를 활용하여 문제를 해결할 수 있는 것 같다. 추후에 dp에 대해서 공부할 때 다시 한 번 풀어봐야겠다. 코드 [Swift] 1 2 3 4 5 6 7 8 9 10 11 12 13 14.. 2021. 11. 16. 15422. Bumped! (Python) https://www.acmicpc.net/problem/15422 15422번: Bumped! The input consists of a single test case. The first line lists five space-separated integers n, m, f, s, and t, denoting the number of cities n (0 < n ≤ 50 000), the number of roads m (0 ≤ m ≤ 150 000), the number of flights f (0 ≤ f ≤ 1 000), th www.acmicpc.net 풀이 어떤 한 지점에서 시작해서 최단 거리를 구하는 문제로 다익스트라를 활용해서 문제를 해결할 수 있다. 이 문제에서 비교해야 할 것은 다음과 같.. 2021. 11. 16. 이전 1 ··· 22 23 24 25 26 27 28 ··· 30 다음
