DFS 2

[백준/C++] 1939번 중량제한

🤔문제 이해 한 공장에서 다른 공장으로 가는 경로 중에서 그 경로 상에 있는 중량 제한 값 중에서 최솟값을 찾고, 그 최솟값 중 가장 큰 것을 출력해주는 문제이다. 💡첫번째 아이디어 DFS를 통해 모든 경로를 탐색해서 그 경로의 가장 작은 중량제한 값을 저장하고 그 값들끼리 비교해서 젤 큰 값을 찾아주면 된다고 생각했다. ❌첫번째 제출 섬이 1만개, 도로가 10만개로 10억번을 다 돌게 되는 첫번째 아이디어 방법으로는 시간초과가 났다. 💡두번째 아이디어 시간초과를 어떻게 해결해야할지 막막해서 질문을 했다. 문제에서 나와있듯 짐의 무게보다 중량제한이 작은 다리를 지나가려는 경우엔 다리가 무너진다고 했다. 이 점을 활용해서 이분탐색을 이용하여 결과를 도출해주면 1초 안에 해결이 가능했다. 🔥풀이🔥 DFS +..

백준/C++ 2022.07.18

[백준/C++] 14716번 현수막

🤔문제 이해 상, 하, 좌, 우, 대각선 4방향으로 인접한 1을 한 글자로 취급하여 글자가 몇개 있는지 구하는 문제이다. 🔥풀이🔥 정말 간단한 BFS 문제인데 방향이 4개 더 추가된 버전이다. 방향을 표현해주는 dx와 dy를 다음과 같이 선언해서 오른쪽, 왼쪽, 위쪽, 아래쪽, 오른쪽 아래, 왼쪽 아래, 오른쪽 위, 왼쪽 위를 나타내주었다. int dx[8] = { 1, -1, 0 , 0 , 1, -1, 1, -1}; int dy[8] = { 0, 0, 1, -1, 1, -1, -1, 1}; #include #include using namespace std; int m, n; int map[251][251]; bool visited[251][251]; queue q; int dx[8] = { 1, -1..

백준/C++ 2022.07.16
728x90