문제

 

풀이

처음 이 문제를 봤을 때 지문에 대한 이해를 전혀 못했습니다.

말을 1인 1개씩 2개를 놓고 게임을 하는건지, 말 1개를 놓고 둘이서 게임을 하는건지도 이해가 안돼서 로직을 그리는 내내 예시도 맞지 않아서 답답했었습니다.

 

문제를 이해하는데 4시간은 걸린것 같습니다.

이 문제는 말을 1개만 놓고 둘이서 게임하는게 맞고, 1번 정점이 루트인 트리라고 명시가 되어있기 때문에 1번 정점부터 방향그래프처럼 순회하도록 합니다.

 

한 번씩 번갈아가면서 점수를 가져가기 때문에 선공의 입장에서는 +, 후공의 입장에서는 -으로 계산할 수 있습니다.

서로 최대한 이기려고 할 것이고, 이기는 경우가 하나라도 존재한다면 이기는 것이기 때문에 가능한 높은 점수를 얻는 것이 중요합니다.

그럴려면 자식 노드의 점수들 중 최솟값을 본인 점수에서 빼는 것으로 계산할 수 있습니다.

선공의 입장에서 계산했기 때문에 해당 노드의 점수가 0 이상이면 선공의 승리, 음수면 후공의 승리가 될 것입니다.

 

2번째 예시로 로직을 설명드리면 루트는 1번, 리프는 4, 5, 6번 노드입니다.

4, 5, 6번 노드에 도착하면 해당 번호만큼 점수를 추가합니다. 그러면 4, 5, 6번 노드의 점수는 4, 5, 6입니다.

 

2번 노드에서는 자신의 번호인 2에서 유일한 자식인 4번 노드의 점수 4를 뺀 값을 저장합니다. 그러면 2번 노드의 점수는 -2가 됩니다.

 

3번 노드는 자식이 2개 있습니다.

5번, 6번 노드의 점수 중 최솟값을 3에서 빼줍니다. 그러면 3번 노드의 점수는 3 - 5 = -2 입니다.

 

마지막 1번 노드입니다.

1번 노드의 자식인 2, 3번 노드 모두 점수가 -2이므로 1 + 2 = 3 점을 얻습니다.

 

그러면 최종 점수 배열은 [3, -2, -2, 4, 5, 6] 이 되고, 0 이상의 점수에는 1, 음수 점수에는 0을 출력하도록 합니다.

 

 

코드

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <vector>
#include <cstring>
#define MAX 100001
using namespace std;
 
vector<int> graph[MAX];
bool visit[MAX];
int score[MAX];
int N;
 
int dfs(int v) {
    visit[v] = true;
 
    int tmp = 1e9;
    for (auto next : graph[v]) {
        if (visit[next]) continue;
        tmp = min(tmp, dfs(next));
    }
    if (tmp == 1e9) tmp = 0;
 
    return score[v] = -tmp + v;
}
 
void func() {
    dfs(1);
 
    for (int i = 1; i <= N; i++) {
        if (score[i] >= 0) cout << "1\n";
        else cout << "0\n";
    }
}
 
void input() {
    int u, v;
    cin >> N;
    for (int i = 1; i < N; i++) {
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'대회 > elice' 카테고리의 다른 글

엘리스 코드 챌린지 Day 6 빨간 선과 파란 선  (0) 2024.07.23
엘리스 코드 챌린지 Day 5 수열 복원  (0) 2024.07.22
엘리스 코드 챌린지 Day 3 문자열 압축 해제  (4) 2024.07.22
엘리스 코드 챌린지 Day 2 정리 정돈을 좋아하는 k씨  (0) 2024.07.22
엘리스 코드 챌린지 Day 1 목표량  (0) 2024.07.22

https://www.acmicpc.net/problem/30893

 

처음 이문제에 접근했을때 문제를 이해하는데 진짜 오래걸렸던 기억이 있어서 다시 풀어봤습니다.

다행히도 백준에 실려있는 문제는 설명이 잘되어있어서 이해하기가 수월하더라고요! 물론 두번째 보는거라 그런거긴 한데

그래도 확실히 게임이론은 어려운것 같습니다..

 

이 문제는 S에서 출발하여 말을 한번씩 번갈아가면서 옮길 수 있고, E에 먼저 도착하는 사람이 이기는 게임으로 선공을 할지, 후공을 할지 구하는 문제입니다.

dfs를 통해서 문제를 접근했고, E에 도착하면 true를 리턴해줍니다.

그다음 자식 노드들 중에서 true인 경우가 하나라도 있으면 true를 리턴해주시면 됩니다

 

"더는 말을 움직일 수 없게 되면 게임이 종료됩니다."

라는 말이 문제에 명시되어 있어서 상대가 자식노드가 없는 정점으로 보내버린다면 게임을 지게됩니다.

이 예외까지 생각하여 true를 최종으로 리턴받는다면 선공을, 아니면 후공을 선택하도록 합니다.

 

 

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
#define MAX 100001
using namespace std;
 
vector<int> graph[MAX];
bool visit[MAX];
int N, S, E, ret;
 
bool dfs(int v, int t) {
    if (v == E) return true;
    visit[v] = true;
 
    int cnt = 0;
    bool flag = false;
    for (auto next : graph[v]) {
        if (visit[next]) continue;
        flag |= dfs(next, 1 - t);
        cnt++;
    }
    if (t && cnt > 1) return false;
 
    return flag;
}
 
void func() {
    if (dfs(S, 0)) cout << "First\n";
    else cout << "Second\n";
}
 
void input() {
    int u, v;
    cin >> N >> S >> E;
    for (int i = 1; i < N; i++) {
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > dfs' 카테고리의 다른 글

boj 19542 전단지 돌리기  (0) 2024.06.19
boj 19236 청소년 상어  (0) 2021.04.22
boj 2239 스도쿠  (0) 2021.04.16
boj 2458 키 순서  (0) 2021.04.13
boj 14889 스타트와 링크  (0) 2021.03.17

https://www.acmicpc.net/problem/19542

 

이 문제는 이해하는데 오래걸린것 같습니다.

"현재 노드에서 거리가 D 이하인 모든 노드에 전단지를 돌릴 수 있다." 라고 문제에 나와있는데

거리가 D 이하인 노드까지만 갈 수 있다 라고 이해를 했어서 어떻게 첫번째 예제의 답이 6이 나오는거지? 생각을 했습니다.

하지만 제 생각을 틀렸었고, "거리가 D 이하인 노드까지는 그곳에 가지 않고도 전달이 가능하다." 라는 말이 맞습니다.

 

그렇다면 dfs를 이용하여 각 노드들의 depth를 구한다음 그 depth가 D 이하라면 전단지를 전달할 수 있게 됩니다.

depth는 리프 노드가 0이고, 자식노드들의 depth 중 최대 + 1로 계산합니다.

depth를 구했다면 D 이하인 depth를 카운팅하면 노드의 갯수를 구할 수 있습니다.

그 다음 거리는 1번 노드까지 돌아와야 하므로 간선의 갯수 * 2로 구할 수 있습니다.

 

 

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 100001
using namespace std;
 
vector<int> v[MAX];
bool visit[MAX];
int dep[MAX];
int N, S, D;
 
int dfs(int x) {
    visit[x] = true;
 
    for (auto next : v[x]) {
        if (visit[next]) continue;
        dep[x] = max(dep[x], dfs(next) + 1);
    }
 
    return dep[x];
}
 
void func() {
    dfs(S);
 
    int ret = 0;
    for (int i = 1; i <= N; i++) {
        ret += (dep[i] >= D);
    }
    cout << max(0, ((ret - 1) << 1)) << '\n';
}
 
void input() {
    int x, y;
    cin >> N >> S >> D;
    for (int i = 1; i < N; i++) {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > dfs' 카테고리의 다른 글

boj 30893 트리 게임  (0) 2024.07.19
boj 19236 청소년 상어  (0) 2021.04.22
boj 2239 스도쿠  (0) 2021.04.16
boj 2458 키 순서  (0) 2021.04.13
boj 14889 스타트와 링크  (0) 2021.03.17

https://www.acmicpc.net/problem/21923

 

21923번: 곡예 비행

동헌이는 모형 비행기 조종 대회에 참가하였다. 이 대회에서는 격자 모양의 공간에서 모형 비행기를 조종하여 얻는 비행 점수로 순위를 매긴다. 격자의 각 칸에는 점수가 부여되어 있고, 비행

www.acmicpc.net

상승 비행을 할 때 지나간 칸에 부여된 점수의 합 + 하강 비행을 할 때 지나간 칸에 부여된 점수의 합을 구합니다.

이 문제의 예제 입력 5번을 보시면 상승 비행과 하강 비행 시 좌표가 겹칠 수 있다는 것을 알 수 있습니다.

따라서 비행이 끝났다는 것은 "좌표가 맨 우측 아래이고, 하강 비행 중일 때"가 됩니다.

 

모든 좌표들을 대상으로 상승, 하강 비행을 해야하며, 기본적인 dfs에 중복 방문 체크를 위해 dp를 사용합니다.

dp[x][y][flag] : 좌표 (x, y)에 flag 상태로 도달했을 때 얻을 수 있는 최대 비행 점수

여기서 flag란 상승 비행인지, 하강 비행인지를 나타내며,

flag = 0이면 상승 비행, flag = 1이면 하강 비행입니다.

그리고 모든 좌표에 대해 상승, 하강 비행을 해야하므로 3차원 배열 dp를 사용합니다.

 

이 문제에서 입력은 음수도 주어지므로 dp를 최솟값으로 초기화해줍니다.

그리고 좌측 아래 좌표 (N - 1, 0)을 시작점으로 dfs 순회합니다.

현재 상승 비행 중이라면 현재 좌표에서 하강 비행으로 변경 후 최대 점수를 먼저 구해줍니다.

그 다음 현재 좌표에 대해 상승 / 하강 비행을 구분하여 다음 좌표로 진행해줍니다.

비행이 끝났을 때는 (N - 1, M - 1)에 하강 비행 중인 상태에 도달했을 때가 되겠고, 해당 좌표값인 list[x][y]를 리턴합니다.

다른 경우에는 ret의 max를 구한 후 자신의 좌표를 더한 값을 리턴합니다.

 

단순 상승만 하는 문제라면 간단하게 구할 수 있었지만 하강 비행이 추가되어 생각이 필요한 문제였습니다.

 

 

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX 1001
using namespace std;
 
int list[MAX][MAX], dp[MAX][MAX][2];
int direct[2][2][2] = { 
    {{0,1},{-1,0}},
    {{0,1},{1,0}}
};
int N, M;
 
int dfs(int x, int y, int flag) {
    if (x == N - 1 && y == M - 1 && flag) {
        return list[x][y];
    }
 
    int& ret = dp[x][y][flag];
    if (ret != -1e9) return ret;
 
    if (!flag) ret = dfs(x, y, !flag);
    for (int d = 0; d < 2; d++) {
        int nx = x + direct[flag][d][0];
        int ny = y + direct[flag][d][1];
 
        if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
 
        ret = max(ret, dfs(nx, ny, flag));
    }
 
    ret += list[x][y];
    return ret;
}
 
void func() {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            for (int k = 0; k < 2; k++) {
                dp[i][j][k] = -1e9;
            }
        }
    }
 
    cout << dfs(N - 1, 0, 0) << '\n';
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 2281 데스노트  (0) 2022.10.08
boj 2015 수들의 합 4  (0) 2022.08.12
boj 12978 스크루지 민호 2  (0) 2022.06.08
boj 10986 나머지 합  (0) 2022.03.08
boj 14238 출근 기록  (0) 2022.02.04

https://www.acmicpc.net/problem/17090

 

17090번: 미로 탈출하기

크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문

www.acmicpc.net

 

https://emoney96.tistory.com/24

 

boj 1103 게임

https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여

emoney96.tistory.com

dfs + dp 문제이며 위의 문제와 비슷한 방법으로 해결하였습니다.

 

대신 게임 문제는 방향이 정해져있지 않아서 4방향 모두 확인해야하지만 이 문제는 1방향만 확인하면 되는 문제입니다.

현재 좌표의 방향으로 이동하면서 맵 밖으로 나가면 1을 리턴, visit으로 사이클을 체크해서 사이클이 발생했으면 0을 리턴합니다.

 

N * M번 모두 돌려가면서 ans를 구하였습니다.

 

 

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static char list[][] = new char[510][510];
    static boolean visit[][] = new boolean[510][510];
    static int dp[][] = new int[510][510];
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int N, M, ans;
 
    static int dfs(int x, int y) {
        if (visit[x][y])
            return 0;
        visit[x][y] = true;
 
        if (dp[x][y] != -1)
            return dp[x][y];
 
        int d = 0;
        if (list[x][y] == 'D')
            d = 1;
        else if (list[x][y] == 'R')
            d = 0;
        else if (list[x][y] == 'U')
            d = 3;
        else
            d = 2;
 
        int nx = x + direct[d][0];
        int ny = y + direct[d][1];
 
        if (nx < 0 || nx >= N || ny < 0 || ny >= M)
            dp[x][y] = 1;
        else {
            dp[x][y] = dfs(x + direct[d][0], y + direct[d][1]);
            visit[nx][ny] = false;    
        }
 
        return dp[x][y];
    }
 
    static void func() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (dp[i][j] != -1) {
                    ans += dp[i][j];
                    continue;
                }
                ans += dfs(i, j);
                visit[i][j] = false;
            }
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = st.nextToken().toCharArray();
            Arrays.fill(dp[i], -1);
        }
 
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 20500 Ezreal 여눈부터 가네 ㅈㅈ  (0) 2022.01.01
boj 1135 뉴스 전하기  (0) 2021.11.15
boj 1648 격자판 채우기  (0) 2021.06.22
boj 14700 넴모넴모 (Hard)  (0) 2021.06.22
boj 1311 할 일 정하기 1  (0) 2021.06.21

https://www.acmicpc.net/problem/1577

 

1577번: 도로의 개수

첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 100보다 작거나 같은

www.acmicpc.net

(0, 0)에서 출발하여 (N, M)에 도착할 수 있는 경우의 수를 구하는문제입니다.

다만 이 문제는 공사중이어서 갈 수 없는 길이 존재하는데 거리는 항상 1이므로 set으로 관리하였습니다.

 

(a, b), (c, d) 형식으로 입력이 주어지면 (a, b)에서 (c, d)로 가는 길, (c, d)에서 (a, b)로 가는 길 모두 체크하였습니다.

로직은 dfs+dp으로 구성하였고, 이동은 최단거리로만 이동하기 때문에 뒤로는 가지 않아야합니다.

 

이 문제의 답은 long long 범위라고 명시되어 있으므로 long long으로 구해줍니다.

 

 

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <set>
#include <cstring>
using namespace std;
typedef long long ll;
 
set<pair<int, int> > s[101][101];
ll dp[101][101];
int list[101][101];
int direct[2][2] = { {0,1},{1,0} };
int N, M, K;
 
ll func(int x, int y) {
    if (x == N && y == M) return 1;
 
    ll &ret = dp[x][y];
    if (ret != -1) return ret;
    ret = 0;
 
    for (int i = 0; i < 2; i++) {
        int nx = x + direct[i][0];
        int ny = y + direct[i][1];
 
        if (nx > N || ny > M) continue;
        if (s[x][y].find({ nx,ny }) != s[x][y].end()) continue;
 
        ret += func(nx, ny);
    }
 
    return ret;
}
 
void input() {
    int sx, sy, ex, ey;
    cin >> N >> M >> K;
    while (K--) {
        cin >> sx >> sy >> ex >> ey;
        s[sx][sy].insert({ ex,ey });
        s[ex][ey].insert({ sx,sy });
    }
    memset(dp, -1, sizeof(dp));
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    cout << func(0, 0) << '\n';
    
    return 0;
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 14700 넴모넴모 (Hard)  (0) 2021.06.22
boj 1311 할 일 정하기 1  (0) 2021.06.21
boj 4781 사탕 가게  (0) 2021.06.19
boj 2186 문자판  (0) 2021.06.19
boj 13325 이진 트리  (0) 2021.06.18

https://www.acmicpc.net/problem/2186

 

2186번: 문자판

첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의

www.acmicpc.net

영어 단어가 "BREAK"처럼 주어지면 문자 판에서 "BREAK"라는 글자가 몇 번 나오는지 구하는 문제입니다.

일단 기본적으로 dfs를 통해 구해주시면 되고, 모든 위치에서 시작할 수 있으니 단어의 첫 알파벳과 일치하는 위치를 시작으로 dfs를 돌려줍니다.

 

하지만 이 문제는 이동 방법이 상하좌우로 K칸까지 이동할 수 있으므로 훨씬 많은 이동이 발생하므로 dp를 같이 사용해줍니다.

dp[x][y][idx] : (x, y)에 도달하였을 때 현재 찾고자 하는 단어의 인덱스가 idx인 경우의 수

이렇게 놓을 수 있습니다.

 

문제의 답은 int범위라고 명시되어 있기때문에 long long은 사용하지 않아도 됩니다.

 

dp를 사용하지 않으면 시간초과가 발생하므로 dp는 필수입니다!!

 

 

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
 
string str;
char list[110][110];
int dp[100][100][81];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N, M, K, strLength;
 
int dfs(int x, int y, int idx) {
    if (idx == strLength) return 1;
 
    int &ret = dp[x][y][idx];
    if (ret != -1) return ret;
    ret = 0;
 
    for (int i = 0; i < 4; i++) {
        for (int j = 1; j <= K; j++) {
            int nx = x + direct[i][0] * j;
            int ny = y + direct[i][1] * j;
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (list[nx][ny] != str[idx]) continue;
 
            ret += dfs(nx, ny, idx + 1);
        }
    }
 
    return ret;
}
 
void func() {
    int ans = 0;
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (list[i][j] != str[0]) continue;
 
            ans += dfs(i, j, 1);
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
        }
    }
    cin >> str;
    strLength = str.size();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 1577 도로의 개수  (0) 2021.06.20
boj 4781 사탕 가게  (0) 2021.06.19
boj 13325 이진 트리  (0) 2021.06.18
boj 1563 개근상  (0) 2021.06.02
boj 10800 컬러볼  (0) 2021.04.09

www.acmicpc.net/problem/19236

 

19236번: 청소년 상어

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는

www.acmicpc.net

이 문제는 고려해야할 부분이 많습니다.

 

상어와 물고기는 8방향 이동을 할 수 있습니다.

순서는 (1)상어가 물고기를 먹고 (2)물고기들이 이동합니다.

상어가 처음에는 (0, 0)에 있는 물고기를 먹으며 먹은 물고기의 방향을 갖게되고, 이후에는 주어진 방향으로만 이동합니다.

 

상어는 한 번에 여러 칸을 이동할 수 있고, 물고기가 있는 칸으로만 이동할 수 있습니다.

따라서 이동경로에 있는 물고기 후보 중 하나를 골라 먹습니다.

 

물고기는 맵 밖이나 상어가 있는 칸으로 이동할 수 없으며 이동할 때 번호가 작은 물고기부터 순서대로 이동합니다. (1번 ~ 16번)

(만약, 해당 번호의 물고기가 먹힌상태면 다음 번호가 이동하면 됩니다.)

물고기는 주어진 방향으로만 1칸 이동하며, 그 칸에 물고기가 있으면 서로의 자리를 바꿉니다.

만약 물고기가 이동할 수 없는 경우에는 이동할 수 있을 때까지 방향을 45도 반시계 방향으로 회전한 후 이동합니다.

 

 

이제 제 로직을 설명하겠습니다.

 

저는 입력을 받으면서 (0, 0)에 상어를 미리 놓고, (1)물고기들 이동, (2)상어 이동 순서대로 구현하였습니다.

func함수의 파라미터에 (현재 배열의 상태(arr), 물고기의 상태(f), 상어의 좌표(X, Y), 상어의 방향(D), 현재 먹은 물고기들의 번호합(S))

을 넘겨주는 재귀함수로 구성하였습니다.

 

함수가 돌 때마다 최대 합을 갱신해주었고, 물고기 이동부터 시작합니다.

먹히지 않은 물고기들만 이동하는 방식이며, 물고기가 이동할 수 있을 때까지 방향을 45도씩 반시계방향으로 회전시키며 반복문을 돌렸습니다.

물고기가 이동하고나면 break를 합니다.

 

이제 상어가 이동합니다.

상어는 한 방향으로만 움직일 수 있지만 여러 칸 이동이 가능하므로 맵 밖으로 나갈 때까지 반복문을 돌려줍니다.

물고기가 없는 칸은 갈 수 없으므로 continue를 하였고, 물고기가 있는 칸은 먹은 후의 상태를 다음 재귀로 넘겨주었습니다. (이는 백트래킹으로 구현하였습니다.)

 

상어와 물고기의 모든 이동이 끝나면 계속 갱신해주었던 답을 출력해줍니다.

 

 

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static class Pair {
        int x, y, d;
 
        public Pair(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int direct[][] = { { -1, 0 }, { -1, -1 }, { 0, -1 }, { 1, -1 }, { 1, 0 }, { 1, 1 }, { 0, 1 }, { -1, 1 } };
    static boolean eat[] = new boolean[17];
    static int ans;
 
    static void func(int[][] arr, Pair[] f, int X, int Y, int D, int S) {
        ans = Math.max(ans, S);
        for (int i = 1; i <= 16; i++) {
            if (eat[i])
                continue;
 
            int x = f[i].x;
            int y = f[i].y;
 
            int nx = x;
            int ny = y;
 
            while (true) {
                nx = x + direct[f[i].d][0];
                ny = y + direct[f[i].d][1];
 
                if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4) {
                    f[i].d = (f[i].d + 1) % 8;
                    continue;
                }
                if (arr[nx][ny] == -1) {
                    f[i].d = (f[i].d + 1) % 8;
                    continue;
                }
 
                if (arr[nx][ny] == 0) {
                    f[i].x = nx;
                    f[i].y = ny;
                    arr[nx][ny] = arr[x][y];
                    arr[x][y] = 0;
                } else {
                    int tmp = arr[x][y];
                    f[arr[nx][ny]].x = x;
                    f[arr[nx][ny]].y = y;
                    f[i].x = nx;
                    f[i].y = ny;
                    arr[x][y] = arr[nx][ny];
                    arr[nx][ny] = tmp;
                }
                break;
            }
        }
 
        int nx = X;
        int ny = Y;
        while (true) {
            nx = nx + direct[D][0];
            ny = ny + direct[D][1];
 
            if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4)
                break;
            if (arr[nx][ny] == 0)
                continue;
 
            int tmp = arr[nx][ny];
            arr[nx][ny] = -1;
            arr[X][Y] = 0;
            eat[tmp] = true;
            int arr2[][] = new int[4][4];
            for (int i = 0; i < 4; i++)
                arr2[i] = arr[i].clone();
            Pair f2[] = new Pair[17];
            for (int i = 1; i <= 16; i++)
                f2[i] = new Pair(f[i].x, f[i].y, f[i].d);
            func(arr2, f2, nx, ny, f[tmp].d, S + tmp);
            eat[tmp] = false;
            arr[nx][ny] = tmp;
            arr[X][Y] = -1;
        }
    }
 
    public static void main(String[] args) throws Exception {
        int list[][] = new int[4][4];
        Pair fish[] = new Pair[17];
 
        int nowx = 0, nowy = 0, nowd = 0, sum = 0;
        int x, d;
        for (int i = 0; i < 4; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 4; j++) {
 
                x = Integer.parseInt(st.nextToken());
                d = Integer.parseInt(st.nextToken()) - 1;
 
                list[i][j] = x;
                fish[x] = new Pair(i, j, d);
                if (i == 0 && j == 0) {
                    list[i][j] = -1;
                    eat[x] = true;
                    nowx = i;
                    nowy = j;
                    nowd = d;
                    sum += x;
                }
            }
        }
        func(list, fish, nowx, nowy, nowd, sum);
        System.out.println(ans);
    }
}
 cs

'algorithm > dfs' 카테고리의 다른 글

boj 30893 트리 게임  (0) 2024.07.19
boj 19542 전단지 돌리기  (0) 2024.06.19
boj 2239 스도쿠  (0) 2021.04.16
boj 2458 키 순서  (0) 2021.04.13
boj 14889 스타트와 링크  (0) 2021.03.17

www.acmicpc.net/problem/17471

 

17471번: 게리맨더링

선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.

www.acmicpc.net

선거구를 두 구간으로 나누는데 나눠진 구간끼리 연결되어 있어야합니다.

 

dfs기반의 부분집합으로 나눌 수 있는 모든 구간을 확인합니다.

두 구간을 div1, div2라는 리스트를 사용하였고, 구역들끼리 연결되어있는지 bfs를 통해 확인합니다.

구간의 모든 구역끼리 연결되어 있으면 구역들의 합의 최솟값을 갱신합니다.

두 선거구로 나눌 수 없는 경우가 입력으로 주어질 수 있으니 그 때는 -1을 출력합니다.

 

 

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    static ArrayList<Integer> graph[] = new ArrayList[11];
    static ArrayList<Integer> div1 = new ArrayList<>();
    static ArrayList<Integer> div2 = new ArrayList<>();
    static int list[] = new int[11];
    static boolean pick[] = new boolean[11];
    static boolean visit[] = new boolean[11];
    static int N, ans = 2147483647;
 
    static boolean bfs(ArrayList<Integer> div, int size, boolean t) {
        Arrays.fill(visit, false);
        Deque<Integer> dq = new ArrayDeque<>();
        dq.add(div.get(0));
        visit[div.get(0)] = true;
        int cnt = 0;
        while (!dq.isEmpty()) {
            int x = dq.poll();
            cnt++;
            for (int i = 0; i < graph[x].size(); i++) {
                int next = graph[x].get(i);
 
                if (visit[next] || pick[next] != t)
                    continue;
 
                visit[next] = true;
                dq.add(next);
            }
        }
 
        if (cnt == size)
            return true;
        else
            return false;
    }
 
    static void func(int idx) {
        if (!div1.isEmpty()) {
            for (int i = 1; i <= N; i++) {
                if (!pick[i])
                    div2.add(i);
            }
            
            if(!div2.isEmpty()) {
                if (bfs(div1, div1.size(), true)) {
                    if (bfs(div2, div2.size(), false)) {
                        int sum = 0;
                        for (int i = 0; i < div1.size(); i++) {
                            sum += list[div1.get(i)];
                        }
 
                        for (int i = 0; i < div2.size(); i++) {
                            sum -= list[div2.get(i)];
                        }
 
                        ans = Math.min(ans, Math.abs(sum));
                    }
                }
                div2.clear();
            }
        }
 
        for (int i = idx; i <= N; i++) {
            div1.add(i);
            pick[i] = true;
            func(i + 1);
            pick[i] = false;
            div1.remove(div1.size() - 1);
        }
    }
 
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
 
        int K, v;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            K = Integer.parseInt(st.nextToken());
            graph[i] = new ArrayList<>();
            while (K-- > 0) {
                v = Integer.parseInt(st.nextToken());
                graph[i].add(v);
            }
        }
    }
 
    static void print() {
        if (ans == 2147483647)
            System.out.println(-1);
        else
            System.out.println(ans);
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(1);
        print();
    }
}
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 17244 아맞다우산  (0) 2021.11.25
boj 1194 달이 차오른다, 가자.  (0) 2021.04.21
boj 2573 빙산  (0) 2021.04.05
boj 14923 미로 탈출  (0) 2021.03.29
boj 17836 공주님을 구해라!  (0) 2021.03.26

www.acmicpc.net/problem/2239

 

2239번: 스도쿠

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다

www.acmicpc.net

백트래킹 기본문제 중 하나입니다.

우선 스도쿠는 9 * 9 배열이 있을 때 각 행, 열, 3 * 3구간에서 1 ~ 9가 한 번씩만 나오게 하는 문제입니다.

 

그럼 각 행, 열, 구간을 중복체크하는 배열을 세개 사용합니다.

(0, 0)부터 (8, 8)까지 한 칸씩 확인하며, list[x][y] != 0이면 수를 넣을 필요가 없으므로 바로 다음좌표를 탐색합니다.

list[x][y] == 0이면 1 ~ 9까지 넣을 수 있는지 확인합니다.

(x, y)에서 숫자 i가 x행에서 사용되었는지, y열에서 사용되었는지, 같은 구간에서 사용되었는지 각각 확인해줍니다.

세 구간 모두 사용되지 않은 숫자만 list[x][y]에 넣어주고 다음좌표로 넘겨줍니다.

모든 좌표를 탐색하였으면 답을 출력하고 리턴합니다.

 

 

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static char div[][] = { { 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c' },
            { 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c' }, { 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c' },
            { 'd', 'd', 'd', 'e', 'e', 'e', 'f', 'f', 'f' }, { 'd', 'd', 'd', 'e', 'e', 'e', 'f', 'f', 'f' },
            { 'd', 'd', 'd', 'e', 'e', 'e', 'f', 'f', 'f' }, { 'g', 'g', 'g', 'h', 'h', 'h', 'i', 'i', 'i' },
            { 'g', 'g', 'g', 'h', 'h', 'h', 'i', 'i', 'i' }, { 'g', 'g', 'g', 'h', 'h', 'h', 'i', 'i', 'i' }, };
    static boolean rowsChk[][] = new boolean[10][10];
    static boolean colsChk[][] = new boolean[10][10];
    static boolean divChk[][] = new boolean[10][10];
    static int list[][] = new int[10][10];
 
    static boolean func(int x, int y) {
        if (x == 9) {
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sb.append(list[i][j]);
                }
                sb.append("\n");
            }
            System.out.println(sb.toString());
            return true;
        }
 
        int nx = x;
        int ny = y + 1;
        if (ny == 9) {
            nx++;
            ny = 0;
        }
 
        if (list[x][y] != 0)
            return func(nx, ny);
        else {
            for (int i = 1; i <= 9; i++) {
                if (rowsChk[x][i] || colsChk[y][i] || divChk[div[x][y] - 'a'][i])
                    continue;
 
                rowsChk[x][i] = true;
                colsChk[y][i] = true;
                divChk[div[x][y] - 'a'][i] = true;
                list[x][y] = i;
                boolean chk = func(nx, ny);
                if (chk)
                    return true;
                list[x][y] = 0;
                divChk[div[x][y] - 'a'][i] = false;
                colsChk[y][i] = false;
                rowsChk[x][i] = false;
            }
        }
 
        return false;
    }
 
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        char ch[];
        for (int i = 0; i < 9; i++) {
            st = new StringTokenizer(br.readLine());
            ch = st.nextToken().toCharArray();
            for (int j = 0; j < 9; j++) {
                list[i][j] = ch[j] - '0';
                if (list[i][j] != 0) {
                    rowsChk[i][list[i][j]] = true;
                    colsChk[j][list[i][j]] = true;
                    divChk[div[i][j] - 'a'][list[i][j]] = true;
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(0, 0);
    }
}
 cs

'algorithm > dfs' 카테고리의 다른 글

boj 19542 전단지 돌리기  (0) 2024.06.19
boj 19236 청소년 상어  (0) 2021.04.22
boj 2458 키 순서  (0) 2021.04.13
boj 14889 스타트와 링크  (0) 2021.03.17
boj 2023 신기한 소수  (0) 2021.03.16

www.acmicpc.net/problem/2458

 

2458번: 키 순서

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여

www.acmicpc.net

 

처음에 이 그림을 보았을 때 위상정렬을 쓰는건가 하고 생각했었지만 순서 중 하나를 출력하는 것이 아닌 자신의 정확한 순서를 알고있는 학생의 수를 출력하는 문제였습니다.

 

저는 두 가지 방법으로 해결하였습니다.

먼저 dfs 방법입니다.

 

저는 2개의 벡터를 사용하였습니다. (자신보다 키가 큰 학생을 저장하는 벡터(f), 작은 학생을 저장하는 벡터(s))

한 학생을 시작으로 두번의 dfs를 수행합니다.

i번 학생보다 키가 큰 학생들을 dfs로 순회하고, 작은 학생들도 똑같이 dfs로 순회합니다.

순회하면서 next의 갯수만큼 cnt를 1씩 늘려줍니다.

 

두 번의 dfs가 끝나고 cnt가 N - 1이면 자신의 정확한 순서를 알 수 있습니다.

 

 

그 다음은 플로이드 방법입니다.

 

d[i][j] : i번 학생의 키 < j번 학생의 키 인 경우

 

플로이드로 자신보다 키가 큰 학생들을 모두 구합니다.

그 다음 i번 학생과 j번 학생의 관계를 확인합니다.

d[i][j] (i번이 j번보다 작은 경우) || d[j][i] (i번이 j번보다 큰 경우)

 

위의 조건을 만족한 횟수가 N - 1이면 자신의 정확한 순서를 알 수 있습니다.

 

dfs
플로이드

 

아무래도 플로이드가  N^3이라 dfs에 비해 속도가 느린 편입니다.

 

 

[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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
vector<int> f[501], s[501];
bool visit[501];
int N, M, cnt;
 
void dfs(vector<int> t[], int v) {
    visit[v] = true;
 
    for (int i = 0; i < t[v].size(); i++) {
        int next = t[v][i];
 
        if (visit[next]) continue;
 
        cnt++;
        dfs(t, next);
    }
}
 
void func() {
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        memset(visit, false, sizeof(visit));
        dfs(f, i);
        memset(visit, false, sizeof(visit));
        dfs(s, i);
 
        if (cnt == N - 1) ans++;
        cnt = 0;
    }
 
    cout << ans << '\n';
}
 
void input() {
    int u, v;
    cin >> N >> M;
    while (M--) {
        cin >> u >> v;
        f[u].push_back(v);
        s[v].push_back(u);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

 

 

[플로이드]

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#define INF 1000000000
using namespace std;
 
bool d[501][501];
int N, M, ans;
 
void solve() {
    for (int i = 1; i <= N; i++) {
        int cnt = 0;
        for (int j = 1; j <= N; j++) {
            if (d[i][j] || d[j][i]) cnt++;
        }
 
        if (cnt == N - 1) ans++;
    }
 
    cout << ans << '\n';
}
 
void func() {
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (d[i][k] && d[k][j]) {
                    d[i][j] = true;
                }
            }
        }
    }
}
 
void input() {
    int u, v;
    cin >> N >> M;
    while (M--) {
        cin >> u >> v;
        d[u][v] = true;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
    solve();
 
 
    return 0;
}
 cs

'algorithm > dfs' 카테고리의 다른 글

boj 19236 청소년 상어  (0) 2021.04.22
boj 2239 스도쿠  (0) 2021.04.16
boj 14889 스타트와 링크  (0) 2021.03.17
boj 2023 신기한 소수  (0) 2021.03.16
boj 14500 테트로미노  (0) 2021.03.15

www.acmicpc.net/problem/1520

 

1520번: 내리막 길

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다.

www.acmicpc.net

emoney96.tistory.com/189

 

boj 1937 욕심쟁이 판다

www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중

emoney96.tistory.com

이 문제와 비슷한 풀이입니다.

dfs + dp를 사용하며

위의 문제는 칸의 수를 세어주었지만 이 문제는 (0, 0)에서 (N - 1, M - 1)까지 도달할 수 있는 경우의 수를 세어주는 문제입니다.

 

현재 칸보다 높이가 더 낮은 지점으로만 이동합니다.

(N - 1, M - 1)에 도달하면 1을 리턴하고 이미 방문한 좌표에는 해당 좌표의 dp[x][y]를 리턴해줍니다.

 

 

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][] = new int[500][500];
    static int dp[][] = new int[500][500];
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int N, M;
 
    static int func(int x, int y) {
        if (x == N - 1 && y == M - 1)
            return 1;
        if (dp[x][y] != -1)
            return dp[x][y];
        dp[x][y] = 0;
 
        for (int i = 0; i < 4; i++) {
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                continue;
            if (list[x][y] <= list[nx][ny])
                continue;
 
            dp[x][y] += func(nx, ny);
        }
        
        return dp[x][y];
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], -1);
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                list[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        System.out.println(func(0, 0));
    }
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 10800 컬러볼  (0) 2021.04.09
boj 12869 뮤탈리스크  (0) 2021.04.04
boj 1937 욕심쟁이 판다  (0) 2021.03.28
boj 2201 이친수 찾기  (2) 2021.03.24
boj 2228 구간 나누기  (0) 2021.03.21

+ Recent posts

티스토리툴바