본문 바로가기

백준189

백준 1504 c++ - [PlusUltraCode] https://www.acmicpc.net/problem/1504 [필자 사고] 그래프 최단거리를 물어보는 문제이다. 특이한 점은 특정 A ,B를 반드시 경유해야 된다는 점이다 다익스트라의 활용도를 극한으로 올려줄 수 있는 문제라고 생각한다. start -> A-> B -> N 인 경우와 start -> B -> A -> N 인 경우가 있다. 다익스트라를 하나 하나 사용하여 각 start->A 와 A->B 와 B->N인 각각의 최단 경로를 합한다. 그 다음 저 두 경로중 작은 값을 출력하면 된다. [소스 코드] #include #include #include #include #include using namespace std; typedef pair Node; vector Arr; vector visit.. 2024. 2. 26.
백준 4963 c++ -[PlusUltraCode] [필자 사고] 전형적인 그래프 탐색 문제이다. 다른 문제와 달리 특이한 점은 대각선의 이동경로 또한 탐색해야 된다는 점이다. 평소 접했던 문제는 동 서 남 북 총 4방향만 탐색경로로 지정 했다면 이 문제는 대각선까지 고려해야 된다. int dx[8] = {1,1,0,-1,-1,-1,0,1}; int dy[8] = { 0,1,1,1,0,-1,-1,-1, }; 수학에서 배웠떤 1사분면 (1,0)에서 시작하여 반시계 방향으로 4사분면 (1,-1) 까지 이동경로를 넣어놓은 배열이다. 나머지는 BFS() 탐색으로 문제를 쉽게 풀 수 있다. [소스 코드] #include #include #include using namespace std; int dx[8] = {1,1,0,-1,-1,-1,0,1}; int dy[8.. 2024. 2. 26.
백준 13549 c++ -[PlusUltraCode] [필자 사고] 이 문제는 최단거리 그래프 탐색 문제이다. 다른 문제와 비슷하지만 이 문제의 특이한 점은 2*N을 할 때 소요시간이 0이라는 점이다 우리가 알고있는 queue를 사용하자니 나중에 들어오는 2*N은 뒤로 밀려 다른 시간들보다 나중에 탐색하게 되는 문제가 발생하게 된다. 그래서 queue가 아닌 priority_queue를 사용하여 0초로 이동한 값은 자연스레 큐 앞에 배치 되도록 설계했다. [소스코드] #include #include #include using namespace std; typedef pair Node; priority_queue pq; vector visited; int N, M; int maxSize = 100001; bool Inside(int num) { if (num.. 2024. 2. 26.
백준 2583 c++ -[PlusUltraCode] [필자 사고] 전형적인 2차원 배열 그래프 탐색문제이다 이 문제의 특이한 점은 좌표로 되어 있다는 것이다. index로만 배열을 다뤄온지라 좌표를 보고 몇십분간 어떻게 해야 오류가 안날지 계쏙 생각하게 되었다. 간단하게 문제 해결방법을 말하겠다. 1. 문제에서 주어지는 빗금친 영역을 배열에 -1로 표시해줬다. 2. 나머지 빗금치지 않은 부분을 BFS탐색을 이용해 넓이를 Resultcount벡터에 넣어줬다. [소스코드] #include #include #include #include using namespace std; typedef struct Rect { int x1, y1, x2, y2; }Rect; int dy[4] = { 0,1,0,-1 }; int dx[4] = { 1,0,-1,0 }; int .. 2024. 2. 23.

티스토리툴바