hwooo

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 BFS 사용해서 최소 이동 횟수를 찾음 코드 #include #include using namespace std; int l; int Moving(int sx, int sy, int ex, int ey) { // 출발 지점 = 도착 지점 if (sx == ex && sy == ey) return 0; int move[8][2] = { {-1,-2}, {-2,-1},{-2,1},{-1,2},{1..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS로 최단 시간을 찾았다. 코드 #include #include using namespace std; int Find(int start, int end) { if (start == end) return 0; int now, next, move[3] = { 1,-1 }; int visited[100001] = { 0, }; queue Q; Q.push(start)..

https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 풀이 BFS를 이용하여 출구까지의 최단 시간을 구함. Escape() 함수는 Q가 다 비워졌을 때가 아닌 출구에 도착했을 때 종료되므로 초기화 시 Q를 비우는 것도 잊지 말아야 함. 코드 #include #include using namespace std; int B[31][31][31]; int L, R, C; bool visited[31][31][31]; queue Q; bool Is_in(int ..

https://www.acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 풀이 BFS로 상근이와 친구부터 찾고, 친구의 친구를 찾았다. 코드 #include #include #include using namespace std; vector V[501]; int BFS(int sang) { int invite = 0, now, cnt; bool visited[501] = { 0, }; queue Q; // 상근이부터 시작 Q.push({ 1, 0 }); v..

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 최단 거리 -> BFS 사용거리가 K인 도시를 찾았다면 오름차순 출력을 위해 우선순위 큐에 해당 도시를 삽입하고, 거리가 K 이상의 도시 정보는 필요하지 않으므로 큐에 삽입하지 않는다. 코드 #include #include #include using namespace std; vector V[300001]; priori..

https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 문제 이해가 안 돼서 찾아보니 A~B~C~D~E의 관계가 있으면 되는 거라 DFS로 풀었다. 같은 출발지여도 중간에 어떤 사람을 선택하냐에 따라 최대 깊이가 달라지므로 선택한 사람을 거친 모든 경로 탐색 후 방문 표시를 없애주었다. 코드 #include #include using namespace std; vector V[2001]; bool visited[2000], CAN = false; void Is_Friend(int now, int cnt) { // A-B-C-D-E 의 경로가 존재함 i..

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 풀이 다익스트라 알고리즘 사용, 상하좌우로 움직이며 방문할 노드의 값이 갱신되면 큐에 삽입. 코드 #include #include using namespace std; int Maze[100][100], Cnt[100][100]; queue Q; void Init(int N, int M) { for (int i = 0; i < N; i++) { for (int j = 0; j..

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 풀이 2를 곱하는 경우와 뒷자리에 1을 붙이는 경우 각각 B보다 작을 경우에 재귀를 돌렸고, B가 됐을 때 cnt 값을 구하여 min 갱신. 이게 왜 BFS인지 모르겠어서 다른 분들 코드를 찾아보니 재귀 대신 큐를 사용하는 코드가 보였다. 확실히 이 방법으로 푼다면 -1을 출력하는 경우를 만들기 더 쉬웠을 것 같다. 코드 #include int min = 0; void Cal(long int now, int end, int cnt) { if (now == end) { if (!min) min = cnt; else if (..