BFS
-
백준 1012 유기농 배추 C++ (BFS)백준 algorithm 2022. 7. 21. 23:31
입력 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다. 출력 각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다. 예제 입력 1 복사 2 10 8 17 0 0 1 0 1 1 4 2 4 3 4 5 2 4 3 4 7 4 8 4 9 4 7 5 8 5 9 5 7 6 8 6 9 6 10 10 1 5 5 예제 출력 1 복사 5 1..
-
프로그래머스 가장 먼 노드 C++프로그래머스(Programmers) 2022. 5. 17. 22:42
=> BFS를 사용해 각 노드로 가는 거리들을 구합니다. => 내가 지금 갈 노드 = 이전 노드 + 1; => 가장 멀리 있는 노드값을 answer에 반환합니다. #include #include #include #include using namespace std; int solution(int n, vector edge) { int answer = 0; vector graph(n+1); for(auto ed : edge) { int from = ed[0]; int to = ed[1]; graph[from].push_back(to); graph[to].push_back(from); } vector dist(n+1, -1); queue q; dist[1] = 0; q.push(1); int max =0; w..
-
프로그래머스 게임 맵 최단거리 C++프로그래머스(Programmers) 2022. 4. 24. 23:47
제한사항 maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다. n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다. maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다. 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다. 입출력 예 mapsanswer [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[..
-
프로그래머스 가장 먼 노드 C++프로그래머스(Programmers) 2022. 4. 22. 22:23
=> BFS문제입니다. => 각 노드들이 맺고 있는 관계들을 벡터로 표현하였습니다. => 이를 vector로 표현하거나 배열로 하거나 편하신대로 하면 됩니다. => 해당 문제에서는 노드의 개수와 간선의 개수가 20,000개 , 50,000개 이므로 벡터를 사용하여 공간의 낭비를 줄였습니다. => 간선들을 표현한 이후에는 항상 사용하던 BFS를 사용하여 문제를 해결하였습니다. https://codingham.tistory.com/168 DFS, BFS code =>BFS 와 DFS code를 사용하기 위해 미리 정리해두었습니다. //int dist[100001]={0}; //bool check[100001];//갔다온지 확인하는 행렬 bool arr[MAX][MAX]; //인접행렬 vector list[M..
-
백준 나이트의 이동 C++백준 algorithm 2022. 4. 13. 23:12
입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다. 출력 각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다. 예제 입력 1 복사 3 8 0 0 7 0 100 0 0 30 50 10 1 1 1 1 => 간단한 BFS문제입니다. => BFS로 탐색을 하며 target 좌표를 찾았을 경우 해당 값까지 이동한 거리를 출력하면 됩니다. => B..
-
백준 7576 - 토마토 C++백준 algorithm 2022. 3. 29. 23:15
입력 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 토마토가 하나 이상 있는 경우만 입력으로 주어진다. 출력 여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 ..
-
백준 2178 - 미로탐색 C++백준 algorithm 2022. 3. 28. 17:45
입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. 출력 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착 위치로 이동할 수 있는 경우만 입력으로 주어진다. 예제 입력 1 복사 4 6 101111 101010 101011 111011 예제 출력 1 복사 15 예제 입력 2 복사 4 6 110110 110110 111111 111101 예제 출력 2 복사 9 예제 입력 3 복사 2 25 1011101110111011101110111 1110111011101110111011101 예제 출력 3 복사 38 예제 입력 4 복사 7 7 1011111 1110001 1000001 10000..
-
프로그래머스 거리두기 확인하기 C++프로그래머스(Programmers) 2022. 2. 21. 23:36
제한사항 places의 행 길이(대기실 개수) = 5 places의 각 행은 하나의 대기실 구조를 나타냅니다. places의 열 길이(대기실 세로 길이) = 5 places의 원소는 P,O,X로 이루어진 문자열입니다. places 원소의 길이(대기실 가로 길이) = 5 P는 응시자가 앉아있는 자리를 의미합니다. O는 빈 테이블을 의미합니다. X는 파티션을 의미합니다. 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다. return 값 형식 1차원 정수 배열에 5개의 원소를 담아서 return 합니다. places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다. 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을..