반응형 Algorithm50 [BackJoon] 백준 1697 숨바꼭질(BFS) 백준 BFS 문제 #1697- 숨바꼭질 https://www.acmicpc.net/problem/1697 사용한 개념 BFS개념를 응용했습니다. 우선 방문한 곳은 check 1차원 배열로 방문여부를 체크하여 방문하지 않은 곳만 방문을 하게끔 만들고, BFS 을 통해 방문하지 않은 곳을 계속해서 탐색하도록 합니다. 여기서 포인트는 방문할 때마다 몇번만에 해당 탐색지점에 왔는지 카운트를 해주는 것입니다. *2에서 5를 찾는 경우 예를 들어 2번에서 시작한다고 치고, 2번에서 *2를 해 4번으로 갔다면, 처음 2번에는 카운트 0을 저장하고 4번에 카운트는 0+1 = 1 입니다. 다음 4번에서 +1을 했다면 5번에는 카운트 0+1+1 = 2 입니다. 이런식으로 2에서 시작해 5번으로 도착할때 카운트는 결국 카운.. 2019. 1. 3. [알고리즘] 다익스트라 최단거리 알고리즘(Dijkstra) 다익스트라 최단거리 알고리즘(Dijkstra) 다익스트라 알고리즘은 워낙 유명하죠 ㅎㅎ 다익스트라 알고리즘은 그래프에 있어서 탐색 시작 노드에서 탐색할 노드까지의 최단거리를 구하는 알고리즘입니다. 다익스트라 알고리즘은 실생활에서도 많이 쓰입니다. 지하철 최단거리 노선을 알려준다거나, 네비게이션 최단 경로를 알려주는 등 굉장히 활용도가 높은 알고리즘 입니다. 일단 노드간 가중치가 있어 최단거리를 구할 수 있습니다. 연결되 노드간 가중치의 합이 최단거리라고 할 수 있기 때문이죠. 아래 전체소스에 주석으로 상세히 적어놓았으나, 몇가지 포인트는 알고있어야 합니다. 원리는 다음과 같습니다. 경로를 통해 지나온 노드간 가중치들의 합이 가장 작은 값을 계속 갱신하며, 최단거리 가중치 합을 구하는 것입니다. 예를 들어.. 2018. 12. 25. [BackJoon] 백준 2606 바이러스(DFS) 백준 DFS 문제#2606 - 바이러스(Virus) https://www.acmicpc.net/problem/2606 사용한 개념 DFS깊이탐색을 이용했습니다.문제를 보면, 결국 무조건 1과 연결되어 있는 컴퓨터 갯수를 새는 것입니다. 컴퓨터 1과 연결되어 있으면 계속 깊이탐색을 해서 연결된 컴퓨터 갯수를 카운트하면 답은 쉽게 나옵니다. 컴퓨터 1과 연결되어있지 않는 또 다른 네트워크 영역은 신경쓸 필요도 없습니다. 따라서 소스에서 보면 알 수 있듯이 DFS(1)을 주어 무조건 시작은 1번 컴퓨터에서 시작함을 알 수 있습니다. DFS 기본 개념을 이해하면 쉽게 풀수있고 DFS를 잘 모르면, 어렵습니다.저는 기본적으로 인접리스트 방식의 DFS 깊이탐색을 했습니다.혹, DFS 기본개념을 모르시면 아래 링크에.. 2018. 12. 11. [BackJoon] 백준 2667 단지번호 붙이기(DFS) 백준 DFS 문제 #2667 - 단지번호붙이기 https://www.acmicpc.net/problem/2667 사용한 개념 1) DFS 저는 깊이탐색을 사용했습니다. 우선, 2차원 배열에서 0이 아닌 1인 경우에 깊이탐색을 시작하여 인접해있는 1을 모두 찾게합니다. 그 다음 다시 탐색을 이어가 0이 아닌 1인경우 다시 깊이탐색을 시작합니다. 여기서 달라지는 점은, 이미 탐색을 했다라는 표시를 하기 위해 임시 변수 값이 CNT의 값을 증가시켜 해당 값으로 매핑시켜 표시합니ㅁ다. 따라서.. 1 1 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0 0 1 인 경우, 2 2 0 0 0 2 0 0 0 0 0 0 0 3 3 4 4 0 3 3 0 4 0 0 3 위와 같이 매핑되는 것입니다... 2018. 12. 4. 이전 1 2 3 4 5 6 7 8 ··· 13 다음 반응형
