본문 바로가기
백준 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..
백준 11403 / 경로 찾기 말 그대로 경로를 찾는 문제다. 진짜 기초적인 그래프 문제 DFS와 BFS를 사용하여 풀 수 있다. DFS 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980#include #include #include #include #include using namespace std; int d[101];int ans[101][101];int arr[101][101];int n;vector a; void check(int num, int now) { for (int i = 0; i > n; for ..
백준 1012 / 유기농 배추 BFS를 이용한 가장 기본적인 문제기 때문에 나중에 한번 더 풀어봐야 겠다. BFS문제 배추가 있는 곳을 큐에 넣지말고 맵을 서치하면서 하나씩 큐에 넣고 인접한 것들에 서치값을 -1로 만들면서 확인하면 된다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include #include #include #include using namespace std;int n, m, w;int map[51][51];int d[51][51];int dx[] = { 1,-1,0..
플로이드 워셜 알고리즘 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 시간복잡도는 O(V^3)O(V3)이다. 다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다는 것이 특징. 플로이드-워셜 알고리즘은 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s와 m까지 가는 데 걸리는 최단거리와 e와 m까지 가는 데 걸리는 최단거리를 이용한다. s : 시작 노드e : 목표 노드m : s와 e 사이의 노드 알고리즘 123456void Floyd_Warshall() { for(m=1; m

티스토리툴바