DFS
-
프로그래머스 전력망을 둘로 나누기 C++프로그래머스(Programmers) 2022. 4. 25. 20:58
제한사항 n은 2 이상 100 이하인 자연수입니다. wires는 길이가 n-1인 정수형 2차원 배열입니다. wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다. 1 ≤ v1 < v2 ≤ n 입니다. 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다. 입출력 예 nwiresresult 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 4 [[1,2],[2,3],[3,4]] 0 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 입출력 예 #1 다음 그림은 주어진 입력을 해결하는 방법 중 하나를 나타낸 것..
-
백준 2606 바이러스 C++백준 algorithm 2022. 3. 31. 01:16
입력 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다. 출력 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다. 예제 입력 1 복사 7 6 1 2 2 3 1 5 5 2 5 6 4 7 예제 출력 1 복사 4 => DFS 문제입니다. => 주어진 정점과 간선들은 배열을 통해 구현해두어야합니다. => arr[MAX][MAX] : 간선을 표현한 배열 => 각 정점이 연결되어 있을 경우 '1'로 표현..
-
프로그래머스 거리두기 확인하기 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을..
-
카카오프렌즈 컬러링 북 C++프로그래머스(Programmers) 2021. 12. 28. 10:45
예제 입출력 m n picture answer 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] 예제에 대한 설명 예제로 주어진 그림은 총 4개의 영역으로 구성되어 있으며, 왼쪽 위의 영역과 오른쪽의 영역은 모두 1로 구성되어 있지만 상하좌우로 이어져있지 않으므로 다른 영역이다. 가장 넓은 영역은 왼쪽 위 1이 차지하는 영역으로 총 5칸이다. #include #include #include #include using namespace std; int arr[101][101]; int UpDownLeftRight [4][2] ={{1,0},{-1,0},{0,1},{0,-1} }; vec..
-
단어변환프로그래머스(Programmers) 2021. 11. 15. 23:28
입출력 예 begin target words return "hit" "cog" ["hot", "dot", "dog", "lot", "log", "cog"] 4 "hit" "cog" ["hot", "dot", "dog", "lot", "log"] 0 입출력 예 설명 예제 #1 문제에 나온 예와 같습니다. 예제 #2 target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다. #include #include #include #include using namespace std; vector wordCheck(51,false); vector wordsBook; int answer =100000; string targetWord; bool compare(string begin, string wor..
-
소수만들기프로그래머스(Programmers) 2021. 11. 10. 22:50
=> DFS를 사용하여 풀 수 있는 문제입니다. => DFS를 사용하며 시작하는 INDEX를 하나씩 늘려가며 중복되는 수의 조합은 제외하였습니다. => DFS를 사용하며 Parameter들의 값이 실제로 올라가는 것인지, 넘기는 값만 올라가는 것인지, 주소를 참조하는 것인지 등을 잘 판단하여 써야 합니다. => 소수인지를 판별하는 함수를 생성하여 소수를 판별하여 전역변수에 소수 여부를 기록하였습니다. *1은 소수가 아니며 2는 소수이므로 미리 표시해둡니다. => 시간초과의 경우에 걸리지 않도록 return문을 잘 넣어줍니다. if(cntAdd == 3) { if(prime[sum]) { cnt++;return; } Prime(sum); if(prime[sum]) { cnt++; } return; } =>..
-
백준 2667 - 단지번호붙이기백준 algorithm 2020. 7. 23. 15:14
=> dfs를 적용하여 풀면 되는 문제입니다. 인접한 곳을 확인할 수 있는 행렬을 생성합니다. 해당 행렬을 통해 현재 확인하고 있는 정점의 주위 행렬을 확인합니다. 주위를 확인해갈때 범위가 넘어가지 않았는지 확인합니다. 더 이상 확인할 곳이 없을 때, 하나의 단지가 끝납니다. 이러한 방식으로 모든 구역에 있는 집들을 확인합니다. #include #include #include #include #include #include using namespace std; int N; int Map[26][26]={0}; bool Visited[26][26]={false}; vector NoHome; int cnt; int dx[4]={-1,1,0,0}; int dy[4]={0,0,1,-1}; void dfs(int..
-
프로그래머스 - 네트워크 C++프로그래머스(Programmers) 2020. 7. 10. 22:15
문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[..