어흥

문제 링크: www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 1. 주의할 점 - DFS, BFS, MST, 한줄 모두 가능 - 허무주의 2. 구현 [BFS] - 시작점을 1로 잡고(아무점이나 상관없다) Queue에 넣고 BFS를 수행한다. 방문하지 않은 Node가 있으면 Result++하고 Queue에 넣는다 #include #include #include using namespace std; vector v[1001];..

문제 링크: www.hackerrank.com/challenges/the-quickest-way-up/problem Snakes and Ladders: The Quickest Way Up | HackerRank Given a Snakes and Ladders board, what is the least number of rolls of the die in which a player can reach the destination square? www.hackerrank.com 0. 유사문제 - 백준의 숨바꼭질 유형 Ex. www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K..

문제 링크: www.acmicpc.net/problem/20005 20005번: 보스몬스터 전리품 입력의 첫째 줄에는 멤멤월드의 지도의 크기를 나타내는 두 정수 M(6 ≤ M ≤ 1000), N(6 ≤ N ≤ 1000)과 플레이어의 수 P(1 ≤ P ≤ 26)가 주어진다. M은 지도의 세로 길이, N은 지도의 가로 길이이다. 입 www.acmicpc.net 1. 주의할 점 - AC가 나와도 필요없는 작업은 하지 않도록 노력한다(Ex. '각 플레이어->보스까지의 거리' 대신 보스->각 플레이어까지의 거리) - 보스가 플레이어에게 도달해도 4방향 이동은 이어서 한다 2. 구현 - 2가지의 방법으로 풀었다(단, BFS의 방법은 같다) (0) 공통(BFS) - 보스를 위치를 기준으로 큐에 담아서 각 플레이어까지..

문제링크: www.acmicpc.net/problem/14923 14923번: 미로 탈출 홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 www.acmicpc.net 1. 주의할 점 - 벽은 최대 1번만 뚫을 수 있으므로, 3차원 배열을 통해 BFS를 진행한다 2. 구현 - Check[][][]배열을 모두 MAX로 초기화한다 - 시작점을 Queue에 넣고 BFS를 수행한다 - CW==0 ? 벽을 뚫은 적 없음 : 벽을 뚫은 적 있음 - 다음 칸이 길이라면, 해당 칸의 Check[][][cw]와 Cv+1값을 비교하여 진출 여부를 판단한다 - 다음 ..

문제 링크: www.acmicpc.net/problem/11964 11964번: Fruit Feast Bessie has broken into Farmer John's house again! She has discovered a pile of lemons and a pile of oranges in the kitchen (effectively an unlimited number of each), and she is determined to eat as much as possible. Bessie has a maximum fullness of \(T\) ( www.acmicpc.net 1. 주의할 점 - 그리디로 접근하지 않도록 한다(예외를 잘 처리하면 가능할지도..?. Ex. 9 5 6) 2. 구현 - ..

문제 링크: www.acmicpc.net/problem/14324 14324번: Rain (Small) The first line of the input gives the number of test cases, T. T test cases follow. The first line of each test case contains two numbers R and C indicating the number of rows and columns of cells on the island. Then, there are R lines of C posi www.acmicpc.net ※ 비슷한 문제: www.acmicpc.net/problem/1113 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 ..

문제 링크: www.acmicpc.net/problem/9879 9879번: Cross Country Skiing The cross-country skiing course at the winter Moolympics is described by an M x N grid of elevations (1 = 0 && nx row >> col; int l = 0, r = 0, mid, result; for (int i = 0; i > arr[i][j]; r = max(r, arr[i][j]); } for (int i = 0; i ..

문제 링크: www.hackerrank.com/challenges/bfsshortreach/problem Breadth First Search: Shortest Reach | HackerRank Implement a Breadth First Search (BFS). www.hackerrank.com 1. 주의할 점 - 각 쿼리마다 사용한 전역변수를 잘 초기화한다 2. 구현 - 시작점에서 다른 Node까지의 거리를 저장하는 Dist[] 배열과 각 Node에 연결된 간선들에 대한 정보를 저장하는 V[] 벡터를 초기화한다 - 넘겨 받은 간선들에 대한 정보를 V[]배열에 저장한다 - 시작점을 Queue에 넣은 이후, BFS를 통해 다음 Node의 Dist가 현재까지의 Dist + 1보다 크다면 갱신하고 Queu..