본문 바로가기

백준189

백준 13913 c++ "숨바꼭질 4" -PlusUltraCode- https://www.acmicpc.net/problem/13913   [필자 사고]bfs 탐색을 활용하여 현재위치에서 상대방의 위치까지의 경로를 찾아야 되는 문제이다.현재위치에서 상대방까지 가는 방식은 숨바꼭질 1,2,3 에서 쉽게 알 수 있따.다만 경로를 저장하는건 다른 방식앋. 무식하게 매번 배열을 만들어서 경로를 저장하고 큐에 저장하게 되면 메모리와 시간초과가 나게 된다. 새로 배운 방식은 vistied배열에 값에 자신의 이전 노드를 저장하는 방식이다.vistied[next] = nowIdx; 방식으로 저장하게 되면 어떤 경로로 진행했는지 알 수 있게 된다. 다음은 아래의 코드 해설이다. 1. 입력 처리 및 초기화먼저, 사용자로부터 출발점 N과 목표점 K를 입력받습니다. 그 후, 방문 여부를 저장.. 2024. 9. 26.
백준 12851 c++ "숨박꼭질2" -PlusUltraCode- https://www.acmicpc.net/problem/12851  [필자 사고]BFS 탐색을 이용하여 원하는 이동할 위치를 우선순위큐에 넣어 탐색을 진행하는 문제이다.이 문제에서 조심해야 될점은 visited관련 방문처리이다.경로가 다르면 같은 장소를 방문해도 문제가 되지 않는다.즉 visited를 우선순위 큐에 넣을때 방문처리를 하는게 아니라방문한 후에 그제서야 visitied 를 true 로 해줘야 된다. 아래는 코드해설이다. priority_queue를 사용하여 출발 지점에서부터 목표 노드 K까지 최단 시간을 구하는 BFS 알고리즘을 설명한다. 여기서 최단 시간을 찾은 후, 최단 시간에 도달하는 경로의 개수를 구하는 방식이다.입력 처리 및 초기화: Input() 함수는 사용자로부터 시작 지점 N.. 2024. 9. 26.
백준 1922 c++ "네트워크 연결" -PlusUltraCode- https://www.acmicpc.net/problem/1922 [필자 사고]최소 스패닝 트리를 이용하며 쉽게 해결할 수 있다. 필자는 입력 받은 가중치들을 벡터에 오름차순으로 정렬 하였다.**** 실수 조심 >> 그 뒤 start와 end 값이 같으면 무시하고 start 와 end 가 현재 같은 Union인지 아닌지를 판다하여 문제를 해결해 나갔다. 아래는 코드 해설이다.설명크루스칼 알고리즘 개요:크루스칼 알고리즘은 가중치가 있는 그래프에서 **최소 스패닝 트리(MST)**를 구하는 알고리즘 중 하나입니다.먼저 모든 간선을 가중치 순서대로 정렬한 후, 사이클을 만들지 않으면서 최소 가중치 간선을 하나씩 선택하여 트리를 만들어 나갑니다.이를 위해 유니온-파인드(Union-Find) 자료구조를 사용해 사.. 2024. 9. 24.
백준 2644 c++ "촌수계산" -PlusUltraCode- https://www.acmicpc.net/problem/2644   [필자 사고]트리형태로 이루어진 촌수를 계산하라는 문제이다. DFS알고리즘과 BFS알고리즘 둘다 사용 가능한 문제이다.필자는 BFS알고리즘을 선택하였다. 선택된 위치부터 모든 경로의 촌수를 저장하는 식으로 문제를 해결했다.논리상 트리형태이지만 처음 리스트를 생성할때는 arr[parent].push-back(child);arr[child].push_back(parent) 와 같이 양방향 리스트로 만들어야 모든 경로를 저장할 수 있다. 아래는 소스 코드 해설이다. 큐를 사용한 BFS 탐색:BFS 방식은 큐를 이용해 출발 노드(p1)에서 시작하여 목표 노드(p2)까지의 최단 거리를 구하는 알고리즘입니다.myQueue는 탐색할 노드를 저장하는.. 2024. 9. 24.

티스토리툴바