본문 바로가기

BOJ

백준 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..
백준 7569 / 토마토 BFS 연습문제 * 절대 2차원배열로 퉁치면 안되는 문제다! 처음엔 2차원배열로 받아서 위/아래로 갈경우 N만큼 증가/감소시켜서 풀어보려고 했으나 그렇게풀면 첫번째 박스의 마지막 행이 두번째 박스의 첫째 행과 연결된다는 큰 오류가 있음을 깨달았다. 그래서 3차원배열로 해결했다. 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105#include#include#include#include..
백준 13913 / 숨바꼭질 4 그냥 가장 빠른 시간만 출력하는 문제였다면 쉬웠지만 경로까지 출력해야되기 때문에 좀 복잡하다. BFS를 사용해야하는 문제. 경로는 구조체와 벡터를 이용하여 출력해야한다. 위의 방법도 한 방법이긴하나 from배열을 만들어서 어디서왔는지 저장한 다음 경로를 역순으로 벡터에 모두 넣고 역 출력하는 것이 가장 좋은 방법이다. 자꾸 시간초과가 뜨길래 편법을 썼다 N이 K보다 클때는 뒤로가는 방법밖에 없기 떄문에 그냥 포문돌려서 출력하니 해결됬다. 코드 (벡터를 이용하여 경로를 출력하는 방법) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667..
백준 7562 / 나이트의 이동 최단 거리 문제니 BFS로 풀면된다. 탐색을 int dx[] = {1,2,2,1,-1,-2,-2,-1 };int dy[] = { 2,1,-1,-2,-2,-1,1,2 }; 로 해야한다는 것이 중요. 테스트케이스마다 모든것들을 초기화시켜줘야하는데 여기서 사용한 큐도 초기화시켜줘야한다. (그냥 와일문안에 큐를 새로 선언하면 되긴하지만) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include#include#include#include#include using namespace std; int dx[] = {1,2..
백준 2468 / 안전 영역 가장 높은 곳을 알아낸다음 0부터 가장 높은 곳까지 모든 경우에서 비가 찬 곳 1 / 안 찬 곳 0 으로 해서 DFS던 BFS던 인접 영역이 몇갠지 구하면 된다. DFS 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596#include #include #include #include #include #include using namespace std; int n;int map[101][101];int map2[101][101];bo..
백준 2583 / 영역 구하기 처음엔 그림에 나와있는대로 빈공간은 0, 종이구간은 1인 배열을 만들어 풀어보려고 했다. 온갖 테스트케이스를 넣어봐도 정답이 나왔지만 제출하니 계속 '틀렸습니다'. 어디서 틀린건지 찾느라 시간 많이썼다... 문제는 빈공간이 0, 종이구간 1인 배열을 만들지말고 그냥 순수하게 공간이 아닌 점으로 풀면 되는거였다. (면으로 풀면 답이나오긴 하던데...) BFS와 DFS 둘다 사용해서 해결할 수 있다 DFS 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687#inclu..

티스토리툴바