⭐️ 난이도 Gold 5 ⭐️ 문제 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net ⭐️ Idea flow 일반적인 BFS 문제에 z축이 추가된 문제였다. [전체적인 알고리즘] 1. 빌딩의 층 수, 가로, 세로의 길이를 받는다. 2. 빌딩의 대한 정보를 받으면서 'S'를 입력 받으면 queue에 push 한다. 3. BFS를 실행하면서 비어있는 곳을 다음 방문 위치로 선정한다. 방문한 현재의 위치는 '.'(빈 칸)에서 'x'(방문)으로 바꿔주어 방문..
Coding test/Baekjoon
⭐️ 난이도 Gold 5 ⭐️ 문제 https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 여태 다른 그래프 문제들과는 다르게 USADO라는 단어를 통해 문제를 설명해서, 얼핏 보면 어마무시해보이는 문제였다. 문제를 읽고 정리를 해보자. 1) 1~n까지 번호가 붙어있는 n개의 동영상이 있다. 2) 1~n개의 영상들 중에 n-1개의 가중치가 있는 간선이 있다. 3) USADO란 어떤 두 개의 영상에 있..
⭐️ 난이도 Silver 1 ⭐️ 문제 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net ⭐️ Idea flow 이 문제에서는 간선이 주어지지 않았다. 직접 계산해서 추가를 해야 한다. 집, 편의점, 페스티벌의 위치가 주어지기 때문에, 각 지점에서 다른 지점까지의 거리가 맥주 20병으로 갈 수 있는 거리인지 확인한다. 만일 맥주 20병으로 갈 수 있는 거리라면(50m * 20병 = 1000m) 간선 정보에 추가해준다. 간선을 추가했다면 그 ..
⭐️ 난이도 Gold 5 ⭐️ 문제 https://www.acmicpc.net/problem/6416 6416번: 트리인가? 트리는 굉장히 잘 알려진 자료 구조이다. 트리를 만족하는 자료 구조는 비어 있거나(노드의 개수가 0개), 노드의 개수가 1개 이상이고 방향 간선이 존재하며 다음과 같은 조건을 만족해야 한다. www.acmicpc.net ⭐️ Idea flow 우선 input에서 정점이 몇 개 있는지 알려주지 않는다. 대신 간선의 정보를 입력 받으면서 연결되는 두 정점의 번호와 정점의 개수를 알 수 있다. 정점의 개수를 미리 알 수 없으니 배열이나 vector를 선언하여 미리 할당하는 것이 불가능하다. 따라서 unordered_map edge를 선언하여 key에는 시작하는 정점의 번호, value(..
⭐️ 난이도 Gold 4 ⭐️ 문제 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net ⭐️ Idea flow 문제에서 "트리는 사이클이 없는 연결 요소"라는 조건을 주었다. input에서 정점과 간선의 개수를 입력받고, 간선에 대한 정보(간선이 잇는 두 노드의 숫자)가 주어진다. 이를 통해 양방향 간선을 추가하여 그래프를 형성할 수 있다. 이후 BFS/DFS를 통해 간선을 타고 탐색한다. 탐색을 하던 도중 이미 방문한 노드에 도..
⭐️ 난이도 Gold 4 ⭐️ 문제 https://www.acmicpc.net/problem/4256 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 각 테스트 케이스마다 이진 트리의 전위 순회, 중위 순회의 결과가 주어진다. 이때, 이진 트리의 후위 순회의 결과를 구하시오. ⭐️ Idea flow 문제에서 전위 순회(preorder)과 중위 순회(inorder)의 결과가 주어진다. 전위 순회를 root 노드를 먼저 방문하는 방법이고, 중위 순회는 root 노드를 중간에 방문하는 방법이다. 이와 같..
