각 칸에 오른쪽으로 얼마나 갈 수 있는지 적혀있고, 그 규칙대로 마지막 칸까지 도달했을 때, 최소 몇 번 점프해야 갈 수 있는지 구하는 문제다.
int dp[i]
i번째 칸에 왔을 때, 최소 몇 번 점프해서 왔는지 기억하는 배열
초기 dp는 int의 최댓값으로 잡는다. 점프 수의 최솟값을 구하기 위함이다.
dp 과정
// 맨 첫 칸은 점프를 하지 않았으므로 0
dp[1] = 0;
for(int i = 1; i < n; i++){
// j : i번째 칸에서 점프해서 갈 수 있는 칸(j)에 대해서 최소 점프 수 검사.
for(int j = i + 1; j <= min(arr[i] + i, n); j++){
dp[j] = min(dp[i] + 1, dp[j]);
}
}
코드
#include <bits/stdc++.h>
using namespace std;
int n, arr[1001], dp[1001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> arr[i];
dp[i] = 2147000000;
}
dp[1] = 0;
for(int i = 1; i < n; i++){
for(int j = i + 1; j <= min(arr[i] + i, n); j++){
dp[j] = min(dp[i] + 1, dp[j]);
}
}
if(dp[n] == 2147000000) cout << -1;
else cout << dp[n];
}
vector<pair<int, char>> Rotate; : 뱀의 회전 방향 및 시간 이다.
수도 코드는 이렇다.
int main() {
// 문제의 입력을 받는다.
while(-1){
// 뱀의 머리 위치와 방향을 토대로 다음 머리 위치를 찾는다.
// 방향을 바꿔야 한다면, 방향을 바꿔준다
// 다음 머리 위치에 벽이 있는지 확인한다.
// 다음 머리 위치에 뱀의 몸통이 있는지 확인한다.
// 위 두 가지 조건을 만족하면, 더이상 뱀이 앞으로 전진할 수 없다는 의미이므로 break;
// 다음 머리 위치에 사과가 있는지 확인한다.
// 사과가 있다면, 뱀을 다음 머리를 머리로 인정하고, 기존 머리를 몸통으로 인정한다.
// 사과가 없다면, 뱀의 다음 머리를 머리로 인정하고, 맨 마지막 꼬리를 잘라낸다.
// 시간을 1 늘려준다.
}
}
queue<pair<Loc, int>> snake;
큐의 front는 뱀의 머리, 큐의 back은 뱀의 꼬리, 그 중간에 있는 요소들은 뱀의 몸통이라고 가정하였음.
Loc는 좌표를 구조체로 표현. (아래 코드 참조) in는 뱀 머리 방향을 표현.
문제의 입력을 받는다.
struct Loc{
int x;
int y;
Loc(int a, int b) : x(a), y(b) {};
};
// Loc는 뱀의 머리/몸통/꼬리 위치, int는 뱀 머리 방향
queue<pair<Loc, int>> snake;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> k;
for(int i = 1; i <= k; i++){
cin >> x >> y;
// 사과의 좌표 삽입. 두번째 bool은 이 사과를 먹었는 지 기억하는 변수다.
apple.push_back(make_pair(Loc(y, x), false));
}
cin >> l;
for(int i = 1; i <= l; i++){
cin >> x >> c;
// 방향을 바꿔야 할 때를 기억하는 벡터
Rotate.push_back(make_pair(x, c));
}
snake.push(make_pair(Loc(1, 1), RIGHT));
뱀의 머리 위치와 방향을 토대로 다음 머리 위치를 찾는다. 방향을 바꿔야 한다면, 방향을 바꿔준다
const int UP = 0;
const int RIGHT = 1;
const int DOWN = 2;
const int LEFT = 3;
int TURN(int dir, char to){
if(to == 'L') return (dir - 1 == -1) ? 3 : dir - 1;
else if(to == 'D') return (dir + 1 == 4) ? 0 : dir + 1;
}
x = snake.front().first.x;
y = snake.front().first.y;
dir = snake.front().second;
snake.pop();
// 다음 뱀의 머리 위치
int xx = x + dx[dir];
int yy = y + dy[dir];
int ddir = dir;
// 시간 때문에 뱀의 머리 방향을 바꿔야 한다면, 바꿔준다.
// Rotate는 시간 순서로 주어지기 때문에, idx를 선언하여 시간을 기억해 놓는다.
if(idx < l && Rotate[idx].first == t){
ddir = TURN(dir, Rotate[idx].second);
idx++;
}
다음 머리 위치에 벽이 있는지 확인한다.
if(!(xx >= 1 && xx <= n && yy >= 1 && yy <= n)) break;
다음 머리 위치에 뱀의 몸통이 있는지 확인한다.
snake를 전부 순회해서 다음 머리 위치가 snake에 있는 Loc와 일치하는 지 확인한다.
int tmp = snake.size();
for(int i = 1; i <= tmp; i++){
int tx = snake.front().first.x;
int ty = snake.front().first.y;
int tdir = snake.front().second;
snake.pop();
if(tx == xx && ty == yy){
cout << t;
exit(0);
}
snake.push(make_pair(Loc(tx, ty), tdir));
}
위 두 가지 조건을 만족하면, 더이상 뱀이 앞으로 전진할 수 없다는 의미이므로 break;
다음 머리 위치에 사과가 있는지 확인한다. 사과가 있다면, 뱀을 다음 머리를 머리로 인정하고, 기존 머리를 몸통으로 인정한다.
gotApple은 사과가 있는지 확인하는 변수. 뒤에 if문을 위해서 선언해 놓는다.
bool gotApple = false;
for(int i = 0; i < k; i++){
// 사과를 먹지 않았고, 다음 머리에 사과가 존재한다면 => 사과를 먹은 것으로 처리해야함!
if(!apple[i].second && apple[i].first.x == xx && apple[i].first.y == yy){
// 이전 머리를 몸통으로 인정하기
snake.push(make_pair(Loc(x, y), dir));
int temp = snake.size();
// 다음 머리를 머리로 인정하기
// 여기서 뱀의 머리는 snake의 front와 일맥상통.
snake.push(make_pair(Loc(xx, yy), ddir));
if(temp != 0){
for(int i = 1; i <= temp; i++){
int tx = snake.front().first.x;
int ty = snake.front().first.y;
int tdir = snake.front().second;
snake.pop();
snake.push(make_pair(Loc(tx, ty), tdir));
}
}
apple[i].second = true;
gotApple = true;
break;
}
}
사과가 없다면, 뱀의 다음 머리를 머리로 인정하고, 맨 마지막 꼬리를 잘라낸다.
if(!gotApple){
// 이전 머리를 몸통으로 인정하기
snake.push(make_pair(Loc(x, y), dir));
int temp = snake.size();
// 다음 머리를 머리로 인정하기
snake.push(make_pair(Loc(xx, yy), ddir));
for(int i = 1; i <= temp; i++){
int tx = snake.front().first.x;
int ty = snake.front().first.y;
int tdir = snake.front().second;
snake.pop();
// 꼬리 잘라내기
if(i != 1)
snake.push(make_pair(Loc(tx, ty), tdir));
}
}
시간을 1 늘려준다.
t++;
코드
#include <bits/stdc++.h>
using namespace std;
const int UP = 0;
const int RIGHT = 1;
const int DOWN = 2;
const int LEFT = 3;
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
struct Loc{
int x;
int y;
Loc(int a, int b) : x(a), y(b) {};
};
char c;
int n, k, l, x, y, idx, t = 1, dir;
vector<pair<Loc, bool>> apple;
vector<pair<int, char>> Rotate;
queue<pair<Loc, int>> snake;
int TURN(int dir, char to){
if(to == 'L') return (dir - 1 == -1) ? 3 : dir - 1;
else if(to == 'D') return (dir + 1 == 4) ? 0 : dir + 1;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> k;
for(int i = 1; i <= k; i++){
cin >> x >> y;
apple.push_back(make_pair(Loc(y, x), false));
}
cin >> l;
for(int i = 1; i <= l; i++){
cin >> x >> c;
Rotate.push_back(make_pair(x, c));
}
snake.push(make_pair(Loc(1, 1), RIGHT));
while(-1){
x = snake.front().first.x;
y = snake.front().first.y;
dir = snake.front().second;
snake.pop();
int xx = x + dx[dir];
int yy = y + dy[dir];
int ddir = dir;
if(idx < l && Rotate[idx].first == t){
ddir = TURN(dir, Rotate[idx].second);
idx++;
}
if(!(xx >= 1 && xx <= n && yy >= 1 && yy <= n)) break;
int tmp = snake.size();
for(int i = 1; i <= tmp; i++){
int tx = snake.front().first.x;
int ty = snake.front().first.y;
int tdir = snake.front().second;
snake.pop();
if(tx == xx && ty == yy){
cout << t;
exit(0);
}
snake.push(make_pair(Loc(tx, ty), tdir));
}
bool gotApple = false;
for(int i = 0; i < k; i++){
if(!apple[i].second && apple[i].first.x == xx && apple[i].first.y == yy){
snake.push(make_pair(Loc(x, y), dir));
int temp = snake.size();
snake.push(make_pair(Loc(xx, yy), ddir));
if(temp != 0){
for(int i = 1; i <= temp; i++){
int tx = snake.front().first.x;
int ty = snake.front().first.y;
int tdir = snake.front().second;
snake.pop();
snake.push(make_pair(Loc(tx, ty), tdir));
}
}
apple[i].second = true;
gotApple = true;
break;
}
}
if(!gotApple){
snake.push(make_pair(Loc(x, y), dir));
int temp = snake.size();
snake.push(make_pair(Loc(xx, yy), ddir));
for(int i = 1; i <= temp; i++){
int tx = snake.front().first.x;
int ty = snake.front().first.y;
int tdir = snake.front().second;
snake.pop();
if(i != 1)
snake.push(make_pair(Loc(tx, ty), tdir));
}
}
t++;
}
cout << t;
}
평소에 해본 2048 게임. 상하좌우 방향으로 최대 5번 까지만 시행한다고 한다. 5번까지 상하좌우를 고르는 과정을 DFS로 구현하였다.
우선 main 함수에서 2048 초기값을 받고, 그 배열을 기준으로 dfs 수행
DFS
int depth : 상하좌우로 숫자를 몇 번 넘겼는지 확인하는 변수
depth == 5는 5번을 다 수행했다는 의미. 즉, dfs의 종료 조건이 된다.
종료 조건에서 v를 탐색하여 가장 큰 값을 변수 answer에 기억해둔다.
vector<vector<int>> v 와 solve(v, i)
solve(v, i)는 아래 solve 챕터에서 설명되어 있음
간단하게, i는 상하좌우 중 한 곳의 방향을 가리키고, v는 아직 i 방향으로 수행하기 이전의 배열을 넣는다. solve의 반환 값은 i 방향으로 이동을 마친 배열이다.
void dfs(vector<vector<int>> v, int depth){
if(depth == 5){
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
answer = max(answer, v[i][j]);
return;
}
else {
for(int i = 0; i < 4; i++)
dfs(solve(v, i), depth + 1);
}
}
vector<vector<int>> solve(vector<vector<int>> v, int dir)
dir
따로 상하좌우를 나타내는 상수를 선언하여, dir에 들어온 값에 따라 상/하/좌/우를 구분하여 solve를 수행한다.
상하좌우 상수
const int RIGHT = 0;
const int LEFT = 1;
const int UP = 2;
const int DOWN = 3;
solve
dir는 상하좌우 중 한 곳의 방향을 가리키고, v는 아직 dir 방향으로 수행하기 이전의 배열을 넣는다. solve의 반환 값은 dir 방향으로 이동을 마친 배열이다.
dir == LEFT일 경우만 설명하겠다. 나머지의 경우는 다 비슷하고, 인덱스만 조금 바뀐다.
dir == LEFT일 경우
왼쪽으로 모든 숫자를 미는 것을 고려한다.
i
한 줄 씩 왼쪽으로 미니까, 가장 큰 for문인 i를 한 줄 씩 왼쪽으로 미는 용도 로 사용한다.
j
v[i][j]에 들어갈 수 있는 값을 찾는다. 즉, j의 자리에 들어올 숫자를 찾는다.
j는 자리를 위한 인덱스다.
k
v[i][j]에 들어갈 수 있는 값의 후보를 찾는다.
말이 조금 어려운데, v[i][j]의 값과 v[i][k]의 값에 따라서 v[i][j]에 들어갈 값이 달라지기 때문이다. 일단 코드의 주석을 보면서 이해해보자.
if(dir == LEFT){
// i : 모든 행을 검사해야 한다. (LEFT이기 때문에 행이지, UP이나 DOWN이라면 열을 검사해야 할 것이다.
for(int i = 1; i <= n; i++){
// j : v[i][j]에 들어갈 수 있는 값을 찾는다.
for(int j = 1; j <= n; j++){
// k : v[i][j]에 들어갈 수 있는 값의 후보를 찾는다.
for(int k = j + 1; k <= n; k++){
// 뒤의 값이 비어있는 경우에는 값의 후보가 될 수 없다.
// 왜냐하면, 값이 있어야 v[i][j]에 합쳐지거나, 그 뒤에 놓아지거나 할 것이다.
// 따라서 비어있는 경우에는 continue;
if(v[i][k] == 0) continue;
else {
// 값을 찾으려는 자리와 값의 후보의 값이 같다 == 하나의 숫자로 합쳐질 수 있다.
// 예를 들어, 2 0 0 2 와 같은 경우, j == 0, k == 3 이 된 경우라고 생각하자.
if(v[i][k] == v[i][j]){
v[i][j] *= 2;
// 값의 후보는 v[i][j]에 합쳐졌으므로, 0으로 초기화
v[i][k] = 0;
}
// 값을 찾으려는 자리와 값의 후보의 값이 다르다 == 하나의 숫자로 합쳐질 수 없다. 얹어져야 한다.
else {
// 근데 v[i][j]가 비었다? == 값의 후보는 v[i][j]로 들어와야 한다.
// 예를 들어, 0 0 0 2 와 같은 경우, j == 0, k == 3 이 된 경우라고 생각하자.
if(v[i][j] == 0){
v[i][j] = v[i][k];
v[i][k] = 0;
// j를 빼는 이유
// 0 2 0 2 와 같은 경우, j == 0, k == 1 이 된 경우라고 생각하자.
// 위의 코드 두 문장을 거친 이후, 2 0 0 2가 될 것이고, j-for 문이 끝나면서 j가 1이 되면, 앞의 2와 뒤의 2는 합쳐지지 못한다.
// j == 1, k == 3 이 되어서 그냥 2 2 0 0 이 될 것이다.
// 따라서, j를 한 번 빼줌으로써 이를 방지한다.
j--;
}
// 근데 v[i][j]가 비어있지 않다? == 값의 후보는 v[i][j + 1]로 들어와야 한다.
else{
// v[i][j]와 v[i][k]가 바로 붙어있지 않다면?
// 그냥 뒤에 두고, v[i][k]를 비워준다.
if(j + 1 != k){
v[i][j + 1] = v[i][k];
v[i][k] = 0;
}
// v[i][j]와 v[i][k]가 바로 붙어있다면?
// 예를 들어, 2 4 0 0 와 같은 경우, j == 0, k == 1 이 된 경우라고 생각하자.
// 위 if문 코드를 수행하면 2 0 0 0 이 되어버린다.
// 이를 방지해주고자 위와 같은 if 문을 작성했다.
}
}
// 값을 처리했다면, break
break;
}
}
}
}
}
// RIGHT, UP, DOWN 생략
return v;
dir == LEFT를 dir == RIGHT / UP / DOWN으로 전환할 때의 주의점
왼쪽으로 모는 것과 오른쪽으로 모는 것은 for 문을 돌릴 때 숫자의 증가/감소의 차이가 존재한다.
왼쪽으로 모는 것과 위쪽으로 모는 것은 for 문을 돌릴 때 행/열의 인덱스를 주의해야하는 차이가 존재한다.
빙하가 녹는 과정을 bfs로, 빙하가 여러 개로 갈라졌는지 확인하는 과정은 dfs로 체크한다.
바다의 정보를 저장하는 sea[302][302], 높이 h, 너비 w
sea를 받을 때, 1 이상이면 빙하라는 이야기므로, queue< pair<int, int> > ice;에 좌표 정보를 넣어준다,
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
cin >> sea[i][j];
if (sea[i][j] >= 1) ice.push(make_pair(j, i));
}
}
bfs와 dfs를 수행한다.
while (!ice.empty()) {
int iceNum = ice.size();
// 큐에 들어있는 빙하만큼만 큐 탐색
while (iceNum--) {
int cnt = 0;
int x = ice.front().first;
int y = ice.front().second;
ice.pop();
// 1의 시간이 지날 때 동시다발적으로 녹는다.
// 만약 1의 시간이 지나면서, 바로 왼쪽 빙하가 다 녹아서 0이 되었다고 하면, 0이 되었다고 왼쪽 빙하때문에 내 빙하가 1이 더 줄어드는 것을 방지한다. 따라서 visit 배열을 선언해주어야 한다.
visit[y][x] = 1;
// 상하좌우 탐색해서 sea에서 0인 것만 cnt를 늘려준다.
// cnt는 빙하가 녹을 양을 의미한다.
for (int i = 0; i < 4; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (xx >= 1 && xx <= w && yy >= 1 && yy <= h && visit[yy][xx] == 0 && sea[yy][xx] == 0) {
cnt++;
}
}
sea[y][x] = max(0, sea[y][x] - cnt);
// 빙하가 아직 다 녹지 않았다면 push
if (sea[y][x] > 0) {
ice.push(make_pair(x, y));
}
}
// 빙하가 몇 조각으로 나뉘었는지 찾기
memset(visit, 0, sizeof(visit));
int cnt = 0;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
if (visit[i][j] == 0 && sea[i][j] != 0) {
dfs(j, i);
cnt++;
}
}
}
// 조각으로 나뉘지 않고 다 녹았다.
if (cnt == 0) {
cout << 0;
exit(0);
}
// 2조각 이상이다.
else if (cnt != 1) {
cout << answer;
exit(0);
}
answer++;
memset(visit, 0, sizeof(visit));
}
void dfs(int a, int b) {
visit[b][a] = 1;
for (int i = 0; i < 4; i++) {
int aa = a + dx[i];
int bb = b + dy[i];
if (aa >= 1 && aa <= w && bb >= 1 && bb <= h && visit[bb][aa] != 1 && sea[bb][aa] != 0) {
dfs(aa, bb);
}
}
}
코드
#include <bits/stdc++.h>
using namespace std;
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };
int sea[302][302], visit[302][302], h, w, answer = 1;
queue< pair<int, int> > ice;
void dfs(int a, int b) {
visit[b][a] = 1;
for (int i = 0; i < 4; i++) {
int aa = a + dx[i];
int bb = b + dy[i];
if (aa >= 1 && aa <= w && bb >= 1 && bb <= h && visit[bb][aa] != 1 && sea[bb][aa] != 0) {
dfs(aa, bb);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> h >> w;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
cin >> sea[i][j];
if (sea[i][j] >= 1) ice.push(make_pair(j, i));
}
}
while (!ice.empty()) {
int iceNum = ice.size();
while (iceNum--) {
int cnt = 0;
int x = ice.front().first;
int y = ice.front().second;
ice.pop();
visit[y][x] = 1;
for (int i = 0; i < 4; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (xx >= 1 && xx <= w && yy >= 1 && yy <= h && visit[yy][xx] == 0 && sea[yy][xx] == 0) {
cnt++;
}
}
sea[y][x] = max(0, sea[y][x] - cnt);
if (sea[y][x] > 0) {
ice.push(make_pair(x, y));
}
}
memset(visit, 0, sizeof(visit));
int cnt = 0;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
if (visit[i][j] == 0 && sea[i][j] != 0) {
dfs(j, i);
cnt++;
}
}
}
if (cnt == 0) {
cout << 0;
exit(0);
}
else if (cnt != 1) {
cout << answer;
exit(0);
}
answer++;
memset(visit, 0, sizeof(visit));
}
}
// 익은 토마토일 경우, 익은 토마토를 기준으로 6 방향으로 나눠 안익은 토마토를 익혀가기 위해서 q에 추가한다.
if (m[i][j][k] == 1) q.push(make_pair(tomato(i, j, k), 0));
// 비어있는 경우, emptyCnt++
else if (m[i][j][k] == -1) emptyCnt++;
// 익지 않은 경우, rareCnt++
else if (m[i][j][k] == 0) rareCnt++;
while (!q.empty()) {
int x = q.front().first.x;
int y = q.front().first.y;
int z = q.front().first.z;
int day = q.front().second;
q.pop();
// day에서 제일 큰 값이 전체 토마토가 다 익는 날짜가 된다.
answer = max(answer, day);
for (int i = 0; i < 6; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
int zz = z + dz[i];
if (isRare(xx, yy, zz)) {
// 이제는 익었으므로 하나 줄여준다.
rareCnt--;
// 익었으므로 1로 표기
m[xx][yy][zz] = 1;
// 익은 토마토를 기준으로 BFS
q.push(make_pair(tomato(xx, yy, zz), day + 1));
}
}
}
코드
#include <bits/stdc++.h>
using namespace std;
struct tomato {
int x;
int y;
int z;
tomato(int a, int b, int c) {
x = a; y = b; z = c;
}
};
int dx[] = { 0, 1, 0, 0, -1, 0 };
int dy[] = { 0, 0, 1, 0, 0, -1 };
int dz[] = { 1, 0, 0, -1, 0, 0 };
int m[101][101][101], _x, _y, _z, emptyCnt, rareCnt, answer = -2147000000;
queue< pair<tomato, int> > q;
bool isRare(int xx, int yy, int zz) {
return xx >= 1 && xx <= _y && yy >= 1 && yy <= _x && zz >= 1 && zz <= _z && m[xx][yy][zz] == 0;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> _x >> _y >> _z;
for (int k = 1; k <= _z; k++) {
for (int i = 1; i <= _y; i++) {
for (int j = 1; j <= _x; j++) {
cin >> m[i][j][k];
if (m[i][j][k] == 1) q.push(make_pair(tomato(i, j, k), 0));
else if (m[i][j][k] == -1) emptyCnt++;
else if (m[i][j][k] == 0) rareCnt++;
}
}
}
if (q.size() + emptyCnt == _x * _y * _z) {
cout << 0;
exit(0);
}
while (!q.empty()) {
int x = q.front().first.x;
int y = q.front().first.y;
int z = q.front().first.z;
int day = q.front().second;
q.pop();
answer = max(answer, day);
for (int i = 0; i < 6; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
int zz = z + dz[i];
if (isRare(xx, yy, zz)) {
rareCnt--;
m[xx][yy][zz] = 1;
q.push(make_pair(tomato(xx, yy, zz), day + 1));
}
}
}
if (rareCnt == 0) cout << answer;
else cout << -1;
}
구구절절 말이 길지만, 결국 사람과 사람이 주어질 때, 몇 다리 건너서 만날 수 있는지 구하는 문제였다.
m[101][101] : 사람들의 촌수 계산을 위해 인접행렬을 선언했다.
tar1과 tar2가 몇 다리 건너서 만날 수 있는 지 DFS로 풀어보고자 헀다. DFS는 가장 먼저 찾은 해답이 최단 다리라고 보장하지 못하므로, 사실상 모든 경로를 탐색해야 한다. 그나마 탐색하는 경로를 줄이기 위해, 탐색 여부를 저장하는 visit[101]를 선언한다.
DFS의 종료 조건
내가 탐색하려는 index가 tar2일 때
최단 거리를 저장하는 answer와 cnt를 비교해서 더 작은 값으로 answer를 업데이트한다.
DFS 탐색
// 사람 수 만큼 탐색
for (int i = 1; i <= n; i++) {
// 아직 탐색되지 않은 사람이고, 연결이 되어 있다면 dfs할 수 있다.
if (visit[i] == 0 && m[index][i] == 1) {
visit[i] = 1;
dfs(i, cnt + 1);
visit[i] = 0;
}
}
코드
#include <bits/stdc++.h>
using namespace std;
int m[101][101], visit[101];
int n, a, b, cases, tar1, tar2, answer = 101;
void dfs(int index, int cnt) {
if (index == tar2) {
answer = min(answer, cnt);
}
else {
for (int i = 1; i <= n; i++) {
if (visit[i] == 0 && m[index][i] == 1) {
visit[i] = 1;
dfs(i, cnt + 1);
visit[i] = 0;
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> tar1 >> tar2 >> cases;
for (int i = 1; i <= cases; i++) {
cin >> a >> b;
m[a][b] = 1;
m[b][a] = 1;
}
visit[tar1] = 1;
dfs(tar1, 0);
if (answer == 101) cout << -1;
else cout << answer;
}
처음에 총 숫자의 갯수를 주고, 맨 마지막으로 주는 숫자는 플러스와 마이너스를 한 결과값, 나머지 중간에 있는 숫자는 피연산자들이다.
dp[i][j]
i번째 피연산자를 플러스 또는 마이너스로 계산했을 때, 결과 j가 나오는 경우의 수를 저장한다.
dp[i][j]의 초깃값
첫 피연산자가 k라고 하면, 뺄수는 없으므로 dp[1][k] = 1이 된다.
연산의 초깃값이 k가 되고, k가 될 수 있는 경우의 수가 하나밖에 존재하지 않는다.
dp[i][j]의 탐색
dp[i - 1]를 순회하면서 피연산자 num를 더하거나 뺄 수 있는 후보를 찾는다. 후보를 찾았고, 그 후보에서 num을 더하거나 뺐을 때 0 이상 20 이하라면, dp[i][j + num] += dp[i - 1][j]; 혹은 dp[i][j - num] += dp[i - 1][j];를 한다.
for (int i = 2; i <= n - 1; i++) {
cin >> num;
// dp[i - 1]에서 num을 더하거나 뺄 수 있는 후보 찾기
for (int j = 0; j <= 20; j++) {
// 후보를 찾았다.
if (dp[i - 1][j] > 0) {
// j에서 (후보의 연산 결과 값에서) num을 더하거나 뺐을 때 0이상 20이하라면 그 경우의 수를 더해준다.
if (j + num <= 20) dp[i][j + num] += dp[i - 1][j];
if (j - num >= 0) dp[i][j - num] += dp[i - 1][j];
}
}
}
코드
#include <bits/stdc++.h>
using namespace std;
int n, num;
long long dp[101][21];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> num;
dp[1][num] = 1;
for (int i = 2; i <= n - 1; i++) {
cin >> num;
for (int j = 0; j <= 20; j++) {
if (dp[i - 1][j] > 0) {
if (j + num <= 20) dp[i][j + num] += dp[i - 1][j];
if (j - num >= 0) dp[i][j - num] += dp[i - 1][j];
}
}
}
cin >> num;
cout << dp[n - 1][num];
}
아직 아무 음악을 탐색하지 않았으므로, 0번째 음악 리스트에는 초깃값 S 크기의 볼륨을 가질 수 있다.
즉, dp[0][s] = true;
dp[i][j] 탐색
i번째 음악 볼륨 리스트에서 볼륨을 오르내릴 때, dp[i - 1]를 탐색해서 볼륨을 오르내릴 후보를 찾는다. 후보를 찾고, i번째 음악 볼륨을 오르내려서 범위 내에 있다면, dp[i][오르내린 볼륨 결과]를 true로 만들어준다.
// 음악을 1번 음악부터 n번 음악까지 탐색한다.
for (int i = 1; i <= n; i++) {
// i번째 음악 볼륨을 입력 받는다.
cin >> v;
// j-for문 : dp[i - 1]를 탐색해서 볼륨을 오르내릴 후보를 찾는다.
for (int j = 0; j <= m; j++) {
// 볼륨을 오르내릴 후보를 찾았다
if (dp[i - 1][j]) {
if (j + v <= m) dp[i][j + v] = true;
if (j - v >= 0) dp[i][j - v] = true;
}
}
}
코드
#include <bits/stdc++.h>
using namespace std;
int n, s, m, v;
bool dp[101][1001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> s >> m;
dp[0][s] = true;
for (int i = 1; i <= n; i++) {
cin >> v;
for (int j = 0; j <= m; j++) {
if (dp[i - 1][j]) {
if (j + v <= m) dp[i][j + v] = true;
if (j - v >= 0) dp[i][j - v] = true;
}
}
}
bool flag = false;
for (int i = m; i >= 0; i--) {
if (dp[n][i]) {
cout << i;
flag = true;
break;
}
}
if (!flag) cout << -1;
}
