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
https://www.acmicpc.net/problem/2583백준 2583번 문제입니다. 제가 요즘 공부하고 있는 dfs활용 문제에요. 밑에는 제 코드입니다.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include #include #include #define MAX 101 int grid[MAX][MAX];bool visited[MAX][MAX];int M,N;int size, cnt; void dfs(int grid[MAX][MAX], int r, int c) { visited[r][c] = true; size++; if..
https://www.acmicpc.net/problem/2606 백준 2606번 문제입니다. 이번문제 또한 http://tiger1710.tistory.com/8 이때 풀었던 문제와 다를건 별로 없는거 같아요!11724번 문제는 그래프 한 뭉탱이?의 갯수를 세 주었다면, 이번문제는 한 뭉탱이에 1을 제외한 정점의 갯수만 세어주면 될거같아요!밑에는 제 코드 입니다.1234567891011121314151617181920212223242526272829303132333435#include #include #define MAX 101 int COM[MAX][MAX];bool visited[MAX];int N, M;int cnt; void dfs(int k) { visited[k] = true; for (in..