본문 바로가기

백준/그래프83

백준 2668 c++ "숫자고르기" -PlusUltraCode- https://www.acmicpc.net/problem/2668  [필자 사고] 처음 방문한 index를 재 방문 했을 경우를 구현할수 있냐 없냐를 묻는 문제이다. 필자는 visited를 int 자료형으로 선언하여 부모index 를 저장하게 구현해났다. 조심해야 될점은 중복 방문 될 수 있으니 set으로 중복을 없애주거나 따로 조건을 추가하여야 된다. 아래는 소스코드 자세한 설명이다. DFS 함수 (깊이 우선 탐색)DFS(int startNum, int parentNum, int count) 함수는 깊이 우선 탐색을 수행하는 핵심 함수입니다.먼저 startNum 노드가 이미 방문된 상태인지 확인합니다.만약 visited[startNum]이 -1이 아니라면, 즉 방문된 상태라면 두 가지 경우로 나뉩니다:.. 2024. 9. 30.
백준 1520 c++ "내리막 길" -PlusUltraCode- https://www.acmicpc.net/problem/1520  [필자 사고]처음 이 문제를 접했을 때 BFS 탐색을 이용했따.다만 visited배열을 이용하게 되면 모든 경로의 탐색을 구할 수 없게 되었다.그래서 visited배열을 빼고 작동시키니 시간초과가 발생했다.N과 M이 각각 500이므로 시간복잡도를 생각해보니500*500*4 와 더불어 계속 새로운 경로가 곱해지니 2초가 넘어가게 된다. 그래서 필자는 DFS탐색을 이용하여 DP count누적을 이용하여 문제를 해결 했따.다음은 소스코드 해설이다. Input() 함수:먼저, 배열의 크기 N x M을 입력받고, 2차원 배열 arr과 방문 여부를 기록하는 visited 배열을 초기화한다.arr는 각 지점의 높이를 저장하는 배열이며, visited.. 2024. 9. 27.
백준 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.

티스토리툴바