본문 바로가기

백준147

백준 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.
백준 2468 c++ - [PlusUltraCode] [필자 사고] 이 문제는 전형적인 2차원 배열 탐색문제이다 특이한 점은 물에 잠겨있는 안정 지역의 최댓값을 구해야 한다. 좀 더 효율적인 방법이 있나 생각을 해봤지만 떠오르지 않았고 입력되는 N의 최댓값이 100이므로 시간복잡도 측면에서 문제가 되지 않아 전체 경우의 수를 다 고려해주기로 했다. 물의 높이를 0부터 최대까지 다 고려해 BFS알고리즘을 수행했다. [소스 코드] #include #include #include using namespace std; int dy[4] = { 0,1,0,-1 }; int dx[4] = { 1,0,-1,0 }; vector Arr; vector visited; int N; int maxNum = -1; int ResultCnt = -1; bool Inside(int.. 2024. 2. 23.
14502 백준 c++ -[PlusUltraCode] [필자 사고] 전형적인 2차원 그래프 탐색문제다 이 문제의 특이한 점은 벽을 세운다라는 점이다. 바이러스가 감염되어 다른 배열에 영향을 끼치는 문제는 수도 없이 풀어 봤을 것이다. 문제의 막히는 주요 원인은 어떻게 벽을 세워 BFS탐색을 수행하는 지다. 필자는 다음과 같이 벽을 세우는 방식을 사용했다. 1. space 배열에 0이 들어간 index를 모두 넣어주었다. 2. vis라는 배열에는 bool값을 넣어주었다. 재귀 함수를 이용하여 space 배열내에 있는 모든 x와 y의 값을 Copy_Arr 에 넣어주어 하나 하나 BFS탐색을 진행시켰다. [소스 코드] #include #include #include using namespace std; vector Arr; vector visited; vecto.. 2024. 2. 23.

티스토리툴바