begin에서 target이 될 때까지 DFS탐색을 하면서 총 몇 번에 변환이 완료되는지 구하면 된다. 단어는 오직 한 글자씩만 변할 수 있으니 반복문을 통해서 각각 단어들을 비교해주고 차이가 1이라면 DFS를 재귀 호출해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include #include #include using namespace std; bool vis[51]; int ans = 100000; void DFS(string cur, string target, vector ar, int cnt, int n, int sum) { if (cur == target) { an..

www.acmicpc.net/problem/20165 20165번: 인내의 도미노 장인 호석 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 www.acmicpc.net 백준 대회가 있길래 참여해서 풀어봤는데 테스트 케이스 2개만 맞추고 나머진 실패했다.. 이후에 참고해서 다시 풀어봤는데 조건처리 부분에서 미숙한 부분 때문에 실패한 것 같다. #include #include using namespace std; int n, m, r, x, y, ans; char dir; int ar[105][105], status[105][105]; void f(int x, in..

www.acmicpc.net/problem/19699 19699번: 소-난다! 지난 번 헛간 청약의 당첨우(牛)가 발표됐다. 청약에 당첨된 소들은 날아갈 듯이 기뻐하다가 진짜로 하늘을 날았다. 하지만 이후로 소들은 날 수 없었다. 그러던 어느 날, 꿀벌에게 쏘이면 잠깐 � www.acmicpc.net 최근에 추가된 문제 중 하나이다. 처음엔 백트래킹으로 풀었는데 안 풀려서 그냥 next_permutation으로 풀었다. 입력받은 수를 정렬시키고 m번만큼 sum변수에 더해줘서 그 sum이 소수이면 ans에 추가해준다. #include #include #include using namespace std; bool vis[10001]; void era() { fill(vis, vis + 10001, true)..

www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 처음엔 완전 탐색으로 다리를 전부 놓으면서 최적의 수를 찾는 줄 알았다. 알고리즘 분류를 보니 BFS, DFS여서 어떻게 해야 할지 감이 잘 안 잡혔다. 1. 1차 BFS를 통해 대륙의 번호를 지정해준다. 2. 큐에 땅의 위치를 전부 삽입해준다 3. BFS를 한번 더 돌려서 이동 범위가 바다라면 큐에 삽입해준다 4. 이동 범위가 땅인데 대륙 번호가 같지 않다면 거기까지의 거리를 리턴해준다. #include #incl..

www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도� www.acmicpc.net BFS와 DFS를 연습하기에 좋은 간단한 문제였다. 주의해야 할 점이 있다면 상하좌우뿐만 아니라 대각선에도 땅이 있다면 섬으로 연결시켜줘야 한다. #include #include using namespace std; int ar[51][51]; bool vis[51][51]; int dx[8] = { 0,0,1,-1,-1,1,-1,1 }; int dy[8] = { 1,-1,0,0,-1,-1,1,1 }; ..

www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 문제를 이해하는 것은 어렵지 않다. 인덱스를 돌면서 방문처리 해주는 간단한 문제였는데, 그래프의 탐색중 기초문제같다. #include using namespace std; int ar[1001], tc, n, cnt; bool vis[1001]; void dfs(int cur) { if (vis[cur]) return; vis[cur] =..