백준 1939 / 중량제한 나중에 다시 한번 풀어볼 문제. 지금까지 풀어온 단순한 BFS 문제들과는 달리, BFS와 이진 탐색을 함께 사용하여야 되는 문제다. 섬의 개수와 다리의 개수가 굉장히 많고, 중량의 최대한계도 높기때문에 일반적인 BFS로 풀면 시간초과 / 메모리초과가 나기 떄문이다. 풀이법은 시작부터 중량 X를 실고 출발한다고 가정 목표 섬에 도착하면 X를 높이고, 목표 섬에 도착하지 못하면 X를 낮추는 방식으로 푼다. 코드 (80~90번째 줄이 핵심이다.) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879.. 백준 5427 / 불 BFS 문제 야마돌게하는 반례 때문에 한창을 헤맸다. 13 3* * ** * ** @ * 바로 나갈 수 있는 경우.... 바로 나갈 수 있으면 문제를 안내지 않았을까..... https://www.youtube.com/watch?v=w211KOQ5BMI 이런 어이없는 반례들까지 모두 해결할 수 있게끔 알고리즘을 완벽히 세워야겠다. ------------------------------ '불' 문제와 비슷한 문제가 있었다. 너구린가 고슴도친가가 어딜 빠져나가는 문제. 이런 문제는 문제를 잘 읽고, 불을 먼저 이동시켜야하는지 사람을 먼지 이동시켜야하는지 파악해야한다. 이 문제는 불을 먼저 이동시켜야하므로 (물론 사람을 이동시킨후 불이 사람을 잡아먹게(?)해도 풀 수 있을 듯) 불의 위치를 먼저 큐에 넣었다... 백준 1600 / 말이 되고픈 원숭이 BFS / DP 문제 BFS로 풀었다. 맵을 제외한 check와 d배열에 말짓(?) 횟수를 담을 수 있게 3차원으로 만들었다. !!!!!!!! 문제 제대로 읽고 가로 세로 정확히 파악하자 !!!!!! 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113#include#include#include#include#include#include using .. 백준 1967 / 트리의 지름 접근은 쉬웠지만 구현이 어려웠던 문제. 처음엔 DFS로 풀어보려 시도했으나 (많은 분들이 DFS로 푸셨더라) 시간초과가 자꾸 발생했다. 이유는 맨 밑 자식 노드들 중에서 경로가 가장 긴 자식 노드를 찾고, 그 노드에서 다른 자식 노드들까지의 경로 중 최대값을 구하는 코드였는데 시간 복잡도가 O(N^3)가 나오기때문. 그리하여 BFS로 바꾸어 풀었다. 루트에서 가장 경로가 긴 노드를 찾고 그 노드에서 가장 멀리 있는 노드를 찾는 코드다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808.. 백준 2146 / 다리 만들기 우선 섬을 둘러싼 0들을 (섬넘버, x좌표, y좌표)로 받고 섬 넘버가 다른 좌표끼리의 최소 거리를 구하는 게 끔 짰다. 시간초과가 떠서 별짓을 다했다. 1001 같은 여러 반례들도 처리하느라 힘들었다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013.. 백준 9019 / DSLR 현재까지 수행했던 경로를 string으로 담거나 역추적을 하면 된다. string도 vector처럼 push_back과 pop_back이 가능하니 string으로 푸는 것이 편하다. 역추적하는 방법을 알아봐야겠다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712.. 백준 2573 / 빙산 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다. 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다. 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다. 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다. 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다. ... 계속 시간초과가 나길래 별 짓을 다해봤다. 빙산 부분을 벡터로 받고 빙산부분만 검사하는 코드를 만들어도 시간초과가 뜨길래 찾아보니 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다. 한번에 전부 가라 앉는 경우 0을 출력하는 코드를 추가하면 시간초과가 풀린다. 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다. 코드 12345678910111213141516171819.. 백준 2589 / 보물섬 BFS 문제 성분이 L인 모든 인덱스에서 가장 먼 곳인 지점의 좌표와 거리를 구조체에 담아 비교하면 된다. 구조체는 아직 익숙하지 않아서 한 번 더 풀어볼만한 문제다. 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101#include#include#include#include using namespace std; int n, m;char map[51][51];bool ch[51][51];bool check.. 이전 1 ··· 6 7 8 9 10 11 12 다음
