www.acmicpc.net/problem/15650

 

15650번: N과 M (2)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

N과 M 두번째 문제입니다.

 

첫번째 문제와 다른 점은 고른 수열이 오름차순이라는 점입니다.

순서를 보는 문제라고 생각하시면 됩니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static boolean visit[];
    static int list[];
    static int N, M;
 
    static void dfs(int num, int cnt) {
        if (cnt == M) {
            for (int x : list) {
                sb.append(x + " ");
            }
            sb.append("\n");
            return;
        }
 
        for (int i = num; i <= N; i++) {
            if (visit[i])
                continue;
 
            visit[i] = true;
            list[cnt] = i;
            dfs(i + 1, cnt + 1);
            list[cnt] = 0;
            visit[i] = false;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new int[M];
        visit = new boolean[N + 1];
    }
 
    public static void main(String[] args) throws Exception {
        input();
        dfs(1, 0);
        System.out.println(sb.toString());
    }
}
 cs

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

boj 15652 N 과 M (4)  (0) 2021.01.26
boj 15651 N과 M (3)  (0) 2021.01.26
boj 15649 N 과 M (1)  (0) 2021.01.26
boj 2580 스도쿠  (0) 2021.01.22
boj 1759 암호 만들기  (0) 2021.01.22

www.acmicpc.net/problem/15649

 

15649번: N과 M (1)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

기본적인 백트래킹으로 해결할 수 있는 문제입니다.

 

이 문제에서는 수의 순서를 따지기때문에 1,2,3,4와 1,2,4,3을 다른 수열이라고 보시면 됩니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static ArrayList<Integer> list = new ArrayList<>();
    static boolean[] visit = new boolean[9];
    static int N, M;
 
    static void dfs(int cnt) {
        if (cnt == M) {
            for (Integer x : list) {
                sb.append(x + " ");
            }
            sb.append("\n");
            return;
        }
 
        for (int i = 1; i <= N; i++) {
            if (visit[i])
                continue;
 
            visit[i] = true;
            list.add(i);
            dfs(cnt + 1);
            list.remove(list.size() - 1);
            visit[i] = false;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
    }
 
    public static void main(String[] args) throws Exception {
        input();
        dfs(0);
        System.out.println(sb.toString());
    }
}
 cs

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

boj 15651 N과 M (3)  (0) 2021.01.26
boj 15650 N 과 M (2)  (0) 2021.01.26
boj 2580 스도쿠  (0) 2021.01.22
boj 1759 암호 만들기  (0) 2021.01.22
boj 1062 가르침  (0) 2021.01.22

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

 

2580번: 스도쿠

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루

www.acmicpc.net

스도쿠가 주어지고 빈칸을 채우는 문제입니다.

 

일단 스도쿠를 완성하기 위한 조건으로

3*3 구역, 가로, 세로에 모두 다른 숫자가 와야합니다.

 

우선 빈칸이 0으로 되어있기때문에 ArrayList에 빈칸의 좌표를 모두 넣습니다.

그런 다음 이 빈칸들을 가지고 백트래킹을 돌립니다.

 

현재 좌표에서 1~9를 모두 넣어보고 조건에 맞으면 다음 좌표로 넘어가는 식으로 계속 탐색해주시면 되겠습니다.

 

모든 빈칸을 다 채웠을 때 출력해주시면 됩니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    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 cols[][] = new boolean[9][10];
    static boolean rows[][] = new boolean[9][10];
    static boolean visit[][] = new boolean[9][10];
    static int list[][] = new int[9][9];
    static ArrayList<int[]> e = new ArrayList<>();
    static boolean chk;
 
    static void dfs(int idx) {
        if (idx == e.size()) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    System.out.print(list[i][j] + " ");
                }
                System.out.println();
            }
            chk = true;
            return;
        }
 
        int x = e.get(idx)[0];
        int y = e.get(idx)[1];
        for (int i = 1; i <= 9; i++) {
            if (rows[x][i] || cols[y][i] || visit[div[x][y] - 'a'][i])
                continue;
 
            rows[x][i] = true;
            cols[y][i] = true;
            visit[div[x][y] - 'a'][i] = true;
            list[x][y] = i;
            dfs(idx + 1);
            if (chk)
                return;
            list[x][y] = 0;
            rows[x][i] = false;
            cols[y][i] = false;
            visit[div[x][y] - 'a'][i] = false;
        }
    }
 
    static void input() throws Exception {
        for (int i = 0; i < 9; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 9; j++) {
                list[i][j] = Integer.parseInt(st.nextToken());
                if (list[i][j] == 0) {
                    e.add(new int[] { i, j });
                } else {
                    cols[j][list[i][j]] = true;
                    rows[i][list[i][j]] = true;
                    visit[div[i][j] - 'a'][list[i][j]] = true;
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        dfs(0);
    }
}
cs

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

boj 15650 N 과 M (2)  (0) 2021.01.26
boj 15649 N 과 M (1)  (0) 2021.01.26
boj 1759 암호 만들기  (0) 2021.01.22
boj 1062 가르침  (0) 2021.01.22
boj 9663 N-Queen  (0) 2021.01.22

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

 

1759번: 암호 만들기

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

www.acmicpc.net

간단한 백트래킹 문제입니다.

 

출력이 오름차순이므로 입력으로 주어지는 알파벳을 오름차순으로 먼저 정렬해줍니다.

그 다음 재귀를 통해 알파벳을 추가할 때마다 모음인지 자음인지 확인하여 갯수를 갱신시켜주면서 재귀를 돌려줍니다.

가능한 암호조합을 모두 찾아낸 후에 이 조합이 모음 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
52
53
54
55
56
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 StringBuffer sb = new StringBuffer();
    static char list[] = new char[16];
    static int L, C, a, b;
 
    static void func(int idx, int cnt, String str) {
        if (cnt == L) {
            if (a < 1 || b < 2)
                return;
            sb.append(str).append("\n");
            return;
        }
 
        if (idx >= C)
            return;
 
        for (int i = idx; i < C; i++) {
            if (list[i] == 'a' || list[i] == 'e' || list[i] == 'i' || list[i] == 'o' || list[i] == 'u')
                a++;
            else
                b++;
 
            func(i + 1, cnt + 1, str + list[i]);
 
            if (list[i] == 'a' || list[i] == 'e' || list[i] == 'i' || list[i] == 'o' || list[i] == 'u')
                a--;
            else
                b--;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        L = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < C; i++) {
            list[i] = st.nextToken().charAt(0);
        }
        Arrays.sort(list, 0, C);
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(0, 0, "");
        System.out.print(sb.toString());
    }
}
 cs

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

boj 15650 N 과 M (2)  (0) 2021.01.26
boj 15649 N 과 M (1)  (0) 2021.01.26
boj 2580 스도쿠  (0) 2021.01.22
boj 1062 가르침  (0) 2021.01.22
boj 9663 N-Queen  (0) 2021.01.22

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

 

1103번: 게임

줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는

www.acmicpc.net

그냥 dfs돌리다가 시간초과난 적이 있어서 dp를 같이 사용하였습니다.

 

보드에 적혀있는 숫자에 맞춰서 동전을 움직여서 최대 몇 번 움직일 수 있는지 구하는 문제입니다.

중간에 있는 구멍은 무시해도 되고, 도착지점이 구멍인 경우에는 동전이 빠지므로 이동하지 못합니다.

dfs로 모든 경우를 다 돌아보고 횟수를 구하면 됩니다.

예외처리로 무한루프가 있는 경우 -1을 출력해야하는데, dfs를 돌다가 방문처리된 곳에 다시 한 번 가게 되면 무한루프 판정으로 -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
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[50][50];
    static boolean visit[][] = new boolean[50][50];
    static int dp[][] = new int[50][50];
    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 ans = -1;
        visit[x][y] = true;
        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] * (list[x][y] - '0');
            int ny = y + direct[i][1] * (list[x][y] - '0');
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                continue;
            if (list[nx][ny] == 'H')
                continue;
 
            dp[x][y] = Math.max(dp[x][y], dfs(nx, ny) + 1);
            if (ans == -1)
                return ans;
            visit[nx][ny] = false;
        }
 
        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++) {
            st = new StringTokenizer(br.readLine());
 
            list[i] = st.nextToken().toCharArray();
        }
 
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], -1);
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        ans = dfs(0, 0);
        if (ans != -1)
            ans++;
        System.out.println(ans);
    }
}
 cs

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

boj 9657 돌 게임 3  (0) 2021.01.27
boj 2096 내려가기  (0) 2021.01.22
boj 12852 1로 만들기 2  (0) 2021.01.22
boj 16195 1, 2, 3 더하기 9  (0) 2021.01.22
boj 15993 1, 2, 3 더하기 8  (0) 2021.01.22

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

 

1062번: 가르침

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문

www.acmicpc.net

모든 경우를 다 확인하여 계산하는 백트래킹 문제입니다.

 

먼저, 단어의 시작은 "anta"로 시작되고, 끝은 "tica"로 끝납니다.

따라서 시작과 끝에 사용되는 알파벳인 'a', 'c', 'i', 'n', 't'는 무조건 가르쳐야하는 알파벳입니다.

M이 5보다 작으면 무조건 모든 단어를 읽을 수 없게 되는것이고,

M이 5보다 크거나 같을 때 백트래킹을 이용하여 해결하면 됩니다.

 

이제 모든 알파벳을 대상으로 백트래킹을 돌립니다.

 

여기서 i를 0부터 돌려버리면 abcdint, adcbint와 같은 중복이 발생하므로 next문자부터 돌려줍니다.

 

가르친 알파벳의 갯수가 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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static char list[][] = new char[50][16];
    static boolean alpha[] = new boolean[26];
    static int N, M, ans;
 
    static void init() {
        alpha['a' - 'a'] = true;
        alpha['c' - 'a'] = true;
        alpha['i' - 'a'] = true;
        alpha['n' - 'a'] = true;
        alpha['t' - 'a'] = true;
    }
 
    static void dfs(int idx, int cnt) {
        if (cnt == M) {
            int readCnt = 0;
            for (int i = 0; i < N; i++) {
                boolean chk = true;
                for (int j = 0; j < list[i].length; j++) {
                    if (!alpha[list[i][j] - 'a']) {
                        chk = false;
                        break;
                    }
                }
 
                if (chk)
                    readCnt++;
            }
 
            ans = Math.max(ans, readCnt);
            return;
        }
 
        for (int i = idx; i < 26; i++) {
            if (alpha[i])
                continue;
 
            alpha[i] = true;
            dfs(i + 1, cnt + 1);
            alpha[i] = false;
        }
    }
 
    static void func() {
        if (M < 5) {
            System.out.println(0);
            return;
        }
 
        init();
        dfs(0, 5);
        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();
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

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

boj 15650 N 과 M (2)  (0) 2021.01.26
boj 15649 N 과 M (1)  (0) 2021.01.26
boj 2580 스도쿠  (0) 2021.01.22
boj 1759 암호 만들기  (0) 2021.01.22
boj 9663 N-Queen  (0) 2021.01.22

 

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

 

9663번: N-Queen

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

백트래킹의 대표적인 문제입니다.

퀸은 가로, 세로, 대각선 방향으로 어디든 갈 수 있으므로 서로 공격하지 못하게 하려면 위와 같은 형태가 되어야합니다.

 

문제에서는 위와 같은 형태가 몇 개 나올 수 있는지 출력하는 문제입니다.

 

x을 1씩 올려가면서 dfs를 돌리고 x,y 위치에서 y방향, 대각선 방향의 위치에 다른 퀸이 놓여져 있는지 체크 후에 놓는 방식으로 하였습니다.

 

y방향을 열을 나타내고, 대각선 방향은 /, \방향이 있습니다.

우선 좌표가 이런식으로 되어있습니다.

 

y 좌표는 말 그대로 (x, y)에서 y좌표만 체크해주시면 되고

 

대각선좌표는 이런식입니다.

왼쪽은 /방향 (x + y)를 나타낸것이고, 오른쪽은 \방향 (x - y + N - 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
#include <iostream>
using namespace std;
 
bool col[16], Left[27], Right[27];
int N, ans;
 
void dfs(int x) {
    if (x == N) {
        ans++;
        return;
    }
 
    for (int y = 0; y < N; y++) {
        if (col[y]) continue;
        if (Left[x + y] || Right[x - y + N - 1]) continue;
            col[y] = true;
            Left[x + y] = true;
            Right[x - y + N - 1] = true;
            dfs(x + 1);
            Right[x - y + N - 1] = false;
            Left[x + y] = false;
            col[y] = false;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    cin >> N;
    dfs(0);
    cout << ans << '\n';
 
    return 0;
}
 cs

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

boj 15650 N 과 M (2)  (0) 2021.01.26
boj 15649 N 과 M (1)  (0) 2021.01.26
boj 2580 스도쿠  (0) 2021.01.22
boj 1759 암호 만들기  (0) 2021.01.22
boj 1062 가르침  (0) 2021.01.22

+ Recent posts

티스토리툴바