https://www.acmicpc.net/problem/12851 https://www.acmicpc.net/problem/13549 https://www.acmicpc.net/problem/13913 이전 백준 1697번 문제의 연장선으로 나온 문제입니다. 숨바꼭질2가 제일 어려운거 같고.. 3이 제일 어려웠던 거 같아요.. 4는 어느정도 생각하면 풀리는거 같네요. 코드에 주석으로 설명할게요.밑에는 제 코드입니다. 2020. 2. 12. 수정
https://www.acmicpc.net/problem/1697 백준 9663번 숨바꼭질 문제입니다. 이번 문제도 BFS 알고리즘을 사용해서 풀었어요. DFS로 해결하려면 힘들 것 같아요. 만약 testCase가 50000 1일 경우에 정말 많은 스택공간이 필요하기 때문에 재귀함수는 메모리초과가 날 것 같고, 스택을 이용하면 시간초과가 날것 같기에.. BFS를 활용하는게 좋아보아요. 처음 구현할 때, 1에서 출발하면 *2 나 +1이 중복되서 체크하는 데 문제가 있을거라고 생각했었는데, 어차피 둘다 이동 횟수는 1증가해서 상관 없을 것 같네요..밑에는 제 코드입니다.123456789101112131415161718192021222324252627282930313233343536373839404142#in..
https://www.acmicpc.net/problem/7562 이번문제는 나이트의 이동입니다. BFS활용 문제인데요. 체스판이 주어지면 나이트가 이동하는데, 목적지까지 몇번만에 갈 수 있는지 계산하는 문제입니다. 좌표가 8방향이고, 한 칸씩 이동하는 것이 아닐뿐이고 다른 BFS와 같은 것 같아요. visited 배열을 bool 자료형이 아닌, int 형으로 해서 방문체크를 함과 동시에 몇번만에 이동했는지 체크할 수 있게 했어요.밑에는 제 코드입니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include #include #include ..
https://www.acmicpc.net/problem/2644 백준 2644번 촌수계산 문제입니다. BFS문제이긴한데.. 어째 제가 푼 방법은 DFS인것 같기도 하고.. 원래 부모부터 계산해야되는거 같긴한데.. 그냥 촌수를 알고싶은 두명 중 한명을 택해서 간선의 갯수? 만큼 카운팅을 해줬습니다. 밑에는 제 코드입니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include #include using namespace std; vector cousin;vector visited; int n, m; //n:전체 사람 수/m:관계의 개수 int cal(int from,..
https://www.acmicpc.net/problem/1707 백준 1707번 이분 그래프 문제입니다. 이번에는 C++로 코드를 짰습니다. C로 인접행렬 크기 20000*20000으로 잡으면 메모리 초과가 나는것 같아서.. vector를 이용했습니다. 각 정점으로 이동할 때 마다 1또는 2로 check번호를 매겨서 검사를 할때 인접한 정점과 check번호가 같은 정점이 발견되면 이분그래프가 아닌것이 되겠죠?1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include #include using namespace std; vector graph;int V,..
https://www.acmicpc.net/problem/11403 백준 11403 경로찾기 문제입니다. 이번 문제의 알고리즘은 만약 A->B->C->D 그래프가 있다면 A에서 D로 갈 수 있다는 것을 확인하면 되는데요, 이것을 확인하기 위해서 범위를 점점 좁혀가면서 탐색을 하는 방법으로 코딩하였습니다.예를 들면 A->D로 이동할 수 있다면 B->D로 이동할 수 있는지 확인하면되고 또 이것을 확인하려면 C->D로 이동가능한지 확인하면 됩니다! 결과적으로 A->D로 이동할 수 있다는 결론이 나와요! 밑에는 제 코드입니다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include..
https://www.acmicpc.net/problem/2178 백준 2178번 미로 탐색입니다.최단 거리를 계산할때, 배열에 인덱스에 접근할때마다 전에 있는 인덱스의 cnt를 하나 증가시킨 값을 넣어요. 결국 최종 종착점에는 이동한 거리가 찍히겠죠? 밑에는 제코드예요. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include #include #define MAX 105 using namespace std; typedef struct rc { int r; int c;}Position; int..
https://www.acmicpc.net/problem/9466 백준 9466번 문제예요. 이번 문제를 풀면서 자신이 얼마나 무력한지 깨달았습니다. 이번 문제도 탐색하는 문제였는데요. 이전 문제들과는 달리 재귀함수가 필요한가? 라고 생각했습니다. 단방향 그래프문제기 때문에 백트래킹이 필요없다고 생각했어요. 그래서 그냥 사이클이 발견될때마다 크기를 체크해서 리턴하는 방식으로 코딩했습니다. 그리고 탐색할때마다 방문체크배열을 초기화하면 시간초과가 뜨더라구요.. 그래서 방문체크배열과 완전히탐색이 끝난배열 총 2개를 이용해서 풀었습니다. 밑에는 제 코드입니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647..
https://www.acmicpc.net/problem/1743백준 1743번 문제입니다. 이번에도 탐색을 활용한 문제입니다!밑에는 제 코드입니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include #include #include #define MAX 110 int N, M;int cnt;int size;int trash[MAX][MAX];bool visited[MAX][MAX]; void dfs(int r, int c) { visited[r][c] = true; size++; if (r > 0 && trash[r][c] == trash[r - 1][c] && !v..
https://www.acmicpc.net/problem/10451백준 10451번 문제입니다. 이번 문제는 탐색을 활용하는 문제에요.밑에는 제 코드입니다.1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include #define MAX 1001 int edge[MAX][MAX];bool visited[MAX];int N;void dfs(int cur) { visited[cur] = true; for (int i = 1; i