BOJ 썸네일형 리스트형 백준 11559 / Puyo Puyo 재밌는 문제. BFS를 이용한 지우기와 맵 갱신이 중요한 문제다. 이런 문제는 일일이 맵을 프린트해보고 결과값을 확인 후 수정하는 것이 중요하다. 내가 절었던 부분은. 한번에 세가지 색이 모두 터질때 카운트가 3이 추가되는 것이 아니라 그냥 1로 친다는 점이다. 코드 printmap() : 맵 출력alldown(); 중간에 빈칸이 생겼을 시 끝까지 떨어질 떄까지 재귀로 맵을 갱신한다.mapcheck(): 폭발이 발생하는지 안하는지 체크, 더 이상 폭발이 발생할 수 없다면 종료.erase(): 폭발 구현. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061.. 백준 1726 / 로봇 BFS 문제 그저 최단거리를 찾는 문제아닌, 방향 바꾸는 행위와 1,2,3칸 직진이 추가된 BFS 문제다. check 배열과 최단거리를 담는 d 배열을 방향값까지 추가하여 3차원으로 선언 후. 직진하는 경우와 방향을 바꾸는 경우를 구현했다. 1. 직진하는 경우 3칸까지 갈 수 있기떄문에 자신의 방향 앞에 놓인 값들이 모두 0일떄 직진할 수 있게 구현했다. 2. 방향을 바꾸는 경우 젤 헷갈렸던 부분 동쪽이 1 서쪽 2 남쪽3 북쪽4 이기 떄문에 예를 들어, 동쪽에서 서쪽에서 바꾸는 경우 숫자는 1이 들지만 방향을 두 번(오른쪽,오른쪽) 바꾸어야되기떄문에 이런 경우들을 체크하는 조건문을 걸어두었다. dir + i == 7 || dir + i == 3 dir은 현재 방향, i는 바꾸고자 하는 방향. 동에서 서.. 백준 9372 / 상근이의 여행 아. 열심히 삽질하다 계속 막혀서 해법을 찾아보니 현타가 온 문제다. BFS 문제인척 하지만 그래프에 대한 기본을 묻는 문제. 나라가 N개이면 간선을 최소 몇 번 타야 모든 나라를 돌 수 있을까? N-1개다. 코드 1234567891011121314151617181920212223#include#include using namespace std; int main() { //freopen("Text.txt", "r", stdin); int testcase; cin >> testcase; while (testcase--) { int m, n; cin >> m >> n; for (int i = 0; i > a >> b; } cout 백준 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.. 이전 1 ··· 4 5 6 7 8 9 10 다음
