https://www.acmicpc.net/problem/1600 3차원 BFS 문제이다.dist[i][j][k] 를 (i, j) 위치에 있을 때 현재 남은 말 이동 횟수가 k 인 경우 그때까지 최소 이동거리라고 정의한 뒤, 일반 이동을 하는 경우dist[next_i][next_j][now_k] = min(dist[next_i][next_j][now_k], dist[now_i][now_j][now_k] + 1) 말로 이동하는 경우 k 를 소모하므로dist[next_i][next_j][now_k-1] = min(dist[next_i][next_j][now_k-1], dist[now_i][now_j][now_k] + 1) 이렇게 식을 세운뒤, dist 배열은 초기값을 INF 값 (파이썬은 보통 9876543..
https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 쓸데없이 힘들게 푼 문제이다. 알고리즘 분류가 백트래킹에 브루트포스였는데, 그렇게 풀었으면 더 쉽게 풀었을 것 같다. 전체 경우의 수가 1023가지 밖에 되지 않아서, 그냥 모든 케이스를 순서대로 방문해보면 된다. 각 숫자가 중복으로 쓰일 수 없어서 비트마스킹을 활용한 풀이도 있었다. 나는 DP 에 역추적을 써서 풀었다. 정말 빙빙 돌아서 풀었다 ㅋㅋㅋ 내가 푼 풀이는 2차원 DP ..
https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net BFS를 응용한 단순 구현문제이다. 내가 푼 알고리즘은 다음과 같다. 1. 외곽을 모두 돌면서 빈공간의 위치를 덱에 넣고, 열쇠는 먹은 후 빈공간으로 바꾼다음 위치를 덱에 넣고, 문은 맵에 문 위치를 저장한다. (이때 같은 문이 여러개 있을 수 있으니, 맵에 리스트를 저장한다.) (열쇠는 같은 열쇠가 여러개 있을 수 있으니 집합에 저장한다.) 2. 현재 갖고 있는 열쇠로 열 수 있는 문을 모두 연다. 문을 열..
https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 단순 BFS 문제를 구현하기 어렵게 내면 이렇게 나올 수 있다는 걸 보여준 문제이다.. 2048과 비슷하게 그냥 상하좌우 이동을 구현하고, 모든 경우의 수를 세면 된다. 각 이동마다 가능한 경우의 수가 상하좌우 4방향 이고, 10번을 넘는 이동은 의미가 없으므로 진짜 의미로 모든 경우의 수는 4^10 = 약 100만 의 경우의 수겠지만, 이 경우의..
