BFS
-
[프로그래머스] 리코쳇 로봇 c++Coding Test/programmers 2023. 11. 17. 18:07
문제 설명 문제 바로가기 제한 사항 3 ≤ board의 길이 ≤ 100 3 ≤ board의 원소의 길이 ≤ 100 board의 원소의 길이는 모두 동일합니다. 문자열은 ".", "D", "R", "G"로만 구성되어 있으며 각각 빈 공간, 장애물, 로봇의 처음 위치, 목표 지점을 나타냅니다. "R"과 "G"는 한 번씩 등장합니다. 입출력 예 board result ["...D..R", ".D.G...", "....D.D", "D....D.", "..D...."] 7 [".D.R", "....", ".G..", "...D"] -1 풀이 #include #include #include using namespace std; int n, m; int dist[6] = {1,0,-1,0,1}; queue Q; ve..
-
[프로그래머스] 부대복귀 C++Coding Test/programmers 2023. 9. 15. 12:36
문제 설명 문제 바로가기 강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 1로 동일합니다. 임무를 수행한 각 부대원은 지도 정보를 이용하여 최단시간에 부대로 복귀하고자 합니다. 다만 적군의 방해로 인해, 임무의 시작 때와 다르게 되돌아오는 경로가 없어져 복귀가 불가능한 부대원도 있을 수 있습니다. 강철부대가 위치한 지역을 포함한 총지역의 수 n, 두 지역을 왕복할 수 있는 길 정보를 담은 2차원 정수 배열 roads, 각 부대원이 위치한 서로 다른 지역들을 나타내는 정수 배열 sources, 강철부대의 지역 destination이 주어졌을 때, 주..
-
[Algorithm] DFS( Depth-First Search), BFS(Breadth-First Search)Computer Science/Algorithm 2022. 11. 28. 19:18
1. DFS 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동 로투 노드(혹은 임의의 다른 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식 ▶모든 노드를 방문하고자 하는 경우에 이 방법을 선택 ▶깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함 ▶검색 속도 자체는 BFS에 비해서 느림 ▶ 스택, 재귀함수로 구현 ① 탐색 시작 노드를 스택에 삽입하고 방문처리 ② 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리 ③ 위 과정을 수행할 수 없을때까지 반복 - 노드 방문 시 방문(Visited)여부를 반드시 검사해야 한다. 아니면 무한 루프에 빠질 수 있음. - 탐색 과정이 ..
-
[CS] Graph, TreeComputer Science/CS 2022. 11. 28. 18:44
트리 ⊂ 그래프 그래프 노드(하나의 점)와 노드 간을 연결하는 간선으로 구성된 자료 구조이다. 순환 혹은 비순환 구조를 이룬다. 그래프의 구현 방법은 2가지 방식이 있습니다. - 인접 행렬(adjacency matrix) : 2차원 배열을 사용하는 방식 - 인접 리스트(adjacency list) : 리스트를 사용하는 방식 두 방식의 메모리와 속도 차이는 다음과 같습니다. V : 노드의 개수, E : 간선의 개수 일 때, 인접 행렬은 O(v^2), 인접 리스트는 O(E) 만큼의 메모리 공간이 요구됩니다. 인접 행렬은 O(1), 인접 리스트는 O(V)만큼의 시간이 소요됩니다. 트리 그래프와 같이 노드와 노드 간을 연결하는 간선으로 구성된 자료 구조이다. 트리는 두 개의 노드 사이에 반드시 1개의 경로만을 ..
-
[프로그래머스] 네트워크 c++Coding Test/programmers 2021. 9. 15. 15:21
문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한 사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers..