<stdio.han>

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

[난이도]

- Silver 3

[알고리즘]

- 백트래킹

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static boolean[] checked;
    static int[] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        checked = new boolean[N + 1];
        arr = new int[N];

        backTracking(0);
    }
    static void backTracking(int depth) {
        if (depth == N) {
            for (int i = 0; i < N; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }
        for (int i = 1; i <= N; i++) {
            if (!checked[i]) {
                checked[i] = true;
                arr[depth] = i;
                backTracking(depth + 1);
                checked[i] = false;
            }
        }
    }
}

[풀이]

1. for문을 돌며 만들 수 있는 숫자를 배열에 담아준다.

2. depth 가 N이 됬을경우 배열에 담긴 숫자를 출력해준다.

1번에서 for문을 돌 때 i=1부터 N까지이기 때문에 자동으로 사전순정렬이 된다.

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

[난이도]

- Silver 3

[알고리즘]

- 백트래킹

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static int N, num, min = Integer.MAX_VALUE;
    static int[] arr, list;
    static boolean[] visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String X = br.readLine();
        num = Integer.parseInt(X);
        N = X.length(); // 입력받은 문자열의 자릿수
        arr = new int[N];
        list = new int[N];
        visited = new boolean[N];
        for (int i = 0; i < N; i++) {
            arr[i] = X.charAt(i) - '0';
        }
        backTracking(0);
        System.out.println(min == Integer.MAX_VALUE ? 0 : min); // min이 여전히 Integer.MAX_VALUE 라면 0 출력 아니라면 min 출력
    }

    static void backTracking(int depth) {
        if (depth == N) {
            // int배열 -> 하나씩 꺼내서 하나의 문자열 -> 정수로 변환
            String s = "";
            for (int i : list) {
                s += i;
            }
            int n = Integer.parseInt(s);

            if (num < n) { // 입력값보다 큰 수중에 최솟값
                min = Math.min(min, n);
            }
            return;
        }
        for (int i = 0; i < N; i++) {
            if (!visited[i]) { // 사용하지 않은 숫자라면 사용
                visited[i] = true; // 사용한 숫자는 체크
                list[depth] = arr[i]; // 새로만들어지는 숫자는 list배열에 담아둠
                backTracking(depth + 1);
                visited[i] = false; // 사용 끝났으면 다시 false
            }
        }
    }
}

[풀이]

1. for문을 돌며 각 자리의 숫자를 list에 담아준 후 depth+1 시킨다.

2. depth 가 N이 되었다면 처음에 입력받은 숫자와 비교한다.

3. 비교한 수가 입력값보다 크다면 min을 갱신한다.

4. min이 갱신이안되었다면 0을출력 갱신되었다면 min 출력

for문을 돌며 list배열에 담아준것을 꺼내 비교하려면 

list배열에 담겨져있는 수를 하나의 문자열로 변환 후 문자열을 다시 정수로 변환해준다.

 // int배열 -> 하나씩 꺼내서 하나의 문자열 -> 정수로 변환
            String s = "";
            for (int i : list) {
                s += i;
            }
            int n = Integer.parseInt(s);

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

[난이도]

- Silver 2

[알고리즘]

- BFS

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static char[][] graph;
    static boolean[][] visited;
    static int T, H, W, answer = 0;
    static Queue<int[]> queue;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {-0, 0, -1, 1};
    static ArrayList<int[]> list;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        T = Integer.parseInt(st.nextToken());
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            H = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            graph = new char[H][W];
            visited = new boolean[H][W];
            queue = new LinkedList<>();
            list = new ArrayList<>();
            answer = 0;
            for (int j = 0; j < H; j++) {
                String input = br.readLine();
                for (int k = 0; k < W; k++) {
                    graph[j][k] = input.charAt(k);
                }
            }
            for (int j = 0; j < H; j++) {
                for (int k = 0; k < W; k++) {
                    if (graph[j][k] == '#') { // 양일경우
                        if (!visited[j][k]) { // 방문하지 않은 곳일 경우 bfs 메서드 실행
                            queue.offer(new int[]{j, k});
                            visited[j][k] = true;
                            bfs();
                            answer++;
                        }
                    }
                }
            }
            bw.write(answer + "\n");

        }
        bw.flush();
        bw.close();
        br.close();
    }

    static void bfs() {
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < H && ny >= 0 && ny < W) { // 인덱스 범위 안
                    if (graph[nx][ny] == '#') { // 양일 경우
                        if (!visited[nx][ny]) { // 방문하지 않은경우
                            visited[nx][ny] = true;
                            queue.offer(new int[]{nx, ny});
                        }
                    }
                }
            }
        }
    }
}

[풀이]

1. for문을 돌며 탐색한 위치가 양(#)이면서 체크하지않은 양일경우 bfs()를 실행하고 answer++한다.

2. bfs는 4방탐색을 하며 인덱스 범위 안이면서 양이면서 방문하지 않은 경우 새로 탐색한 위치를 큐에 담는다.

3. answer를 출력한다.

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

[난이도]

- Silver 2

[알고리즘]

- bfs

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[] maze;
    static boolean[] visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        maze = new int[N];
        visited = new boolean[N];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            maze[i] = Integer.parseInt(st.nextToken());
        }
        bfs();
    }
    static void bfs() {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        visited[0] = true;
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int cur = tmp[0];
            int count = tmp[1];
            if (cur == N - 1) { // 도착했다면
                System.out.println(count); // count 출력
                return;
            }
            for (int i = 1; i <= maze[cur]; i++) {
                if (cur + i < N) { // 최대 인덱스를 넘어서지 않는 경우에만
                    if (!visited[cur + i]) { // 방문하지 않은 경우
                        queue.offer(new int[]{cur + i, count + 1});
                        visited[cur + i] = true;
                    }
                }
            }
        }
        System.out.println(-1); // 도착실패 시 출력
    }
}

[풀이]

DP로 풀 수 있는문제이다. 하지만 BFS로 풀었다.

1. 큐에 현재 위치와 몇번 점프했는지를 담는다.

2. 현재위치에서 이동가능한 만큼 반복하며 큐에 담는다. 큐에 담을때 이동했을 때의 위치와 현재까지 점프한 횟수 + 1를 해 큐에담는다.

이 때 이동했을 때의 위치가 최대 인덱스를 넘어서면 메모리초과가 발생하기 때문에 아닌경우에만 하고 방문하지 않은경우에만 큐에 담아준다.

3. 도착했다면 큐에담긴 count를 출력해주고 큐가 empty가 되어서 도착실패시 -1을 출력해준다.

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

[난이도]

- Silver 2

[알고리즘]

- bfs

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int[] dist;
    static boolean[] visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(st.nextToken());
        dist = new int[n + 1];
        visited = new boolean[n + 1];

        st = new StringTokenizer(br.readLine(), " ");
        int p1 = Integer.parseInt(st.nextToken());
        int p2 = Integer.parseInt(st.nextToken());

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        int m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            graph.get(x).add(y);
            graph.get(y).add(x);
        }
        System.out.println(bfs(p1, p2));
    }

    static int bfs(int start, int end) {
        Queue<Integer> queue = new LinkedList<>();
        dist[start] = 0;
        visited[start] = true;
        queue.offer(start);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int i = 0; i < graph.get(cur).size(); i++) {
                if (!visited[graph.get(cur).get(i)]) {
                    dist[graph.get(cur).get(i)] = dist[cur] + 1;
                    if (graph.get(cur).get(i) == end) {
                        return dist[graph.get(cur).get(i)];
                    }
                    queue.offer(graph.get(cur).get(i));
                    visited[graph.get(cur).get(i)] = true;
                }
            }
        }
        return -1;
    }
}

[풀이]

ArrayList<ArrayList<Integer>>를 활용해 가변적 배열처럼 사용한다. 

dist 배열은 p1기준으로 봤을때 각 사람의 촌수를 저장한다.

visited 배열은 이미 촌수를 계산했다면 다시 계산되면 안되기때문에 계산했는지 안했는지 체크하는 배열이다.

큐에 담긴 숫자를 꺼내 해당숫자와 연관이 있으면서 촌수를 계산하지 않은 숫자라면 큐에 꺼낸 숫자의 촌수 + 1을 연관되어있는 숫자에 기록해준다.

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

[난이도]

- Silver 3

[알고리즘]

- bfs

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static boolean[][] visited;
    static int[][] graph;
    static int N, M, answer = 0;

    static int[] dx = {-1, 1, 0, 0}; // 상, 하, 좌, 우
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int T = Integer.parseInt(st.nextToken());
        for (int i = 0; i < T; i++) { // T번 반복
            st = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            graph = new int[N][M];
            visited = new boolean[N][M];
            ArrayList<int[]> list = new ArrayList<>();
            answer = 0;
            for (int j = 0; j < K; j++) { // 양배추 K개의 위치
                st = new StringTokenizer(br.readLine(), " ");
                int X = Integer.parseInt(st.nextToken());
                int Y = Integer.parseInt(st.nextToken());
                graph[X][Y] = 1;
                if (graph[X][Y] == 1) {
                    list.add(new int[]{X, Y});
                }
            }
            for (int k = 0; k < list.size(); k++) {
                int[] tmp = list.get(k);
                int x = tmp[0];
                int y = tmp[1];
                if (!visited[x][y]) { // 이미 체크한 양배추가 아닐 경우에만 bfs메서드 실행
                    bfs(x, y);
                    answer++;
                }
            }
            System.out.println(answer);

        }
        bw.flush();
        bw.close();
        br.close();
    }

    static void bfs(int x, int y) {
        visited[x][y] = true;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = tmp[0] + dx[i];
                int ny = tmp[1] + dy[i];
                if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                    if (graph[nx][ny] == 1) {
                        if (!visited[nx][ny]) {
                            visited[nx][ny] = true;
                            queue.offer(new int[]{nx, ny});
                        }
                    }
                }
            }
        }
    }
}

[풀이]

1. 각 양배추의 위치를 저장한다.

2. 방문하지 않은 양배추일 경우에는 bfs메서드를 실행한다.

3. bfs 메서드 : 4방탐색을 하며 양배추끼리 이어져있는지 확인한다.

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

[난이도]

- Silver 3

[알고리즘]

- bfs

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static int A, K, answer = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        A = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        bfs();
    }
    static void bfs() {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{A, 0});
        boolean[] visited = new boolean[K + 1];
        visited[A] = true;
        while (!queue.isEmpty()) {
            int tmp[] = queue.poll();
            if (tmp[0] == K) {
                System.out.println(tmp[1]);
                return;
            }
            // 연산 1과 연산 2를 둘다 시행한다
            if (tmp[0] * 2 <= K) { // 연산 2
                visited[tmp[0] * 2] = true;
                queue.offer(new int[]{tmp[0] * 2, tmp[1] + 1});
            }
            if (!visited[tmp[0] + 1]) { // 연산 1, // 연산 2로 수행한 수가 연산 1보다 더 적은 연산횟수이기 때문에 이미 연산 2로 수행한 수라면 패스
                queue.offer(new int[]{tmp[0] + 1, tmp[1] + 1});
            }
        }
    }
}

[풀이]

1. 연산 2와 연산 1을 둘다 시행한다.

2. 연산 2가 가능하다면 연산 2를 시행하고. 연산 후의 숫자를 true로 체크한다.

3. 연산 1은 연산 2로 수행한 수가 연산 1보다 무조건 더 적은 연산횟수를 가지기 때문에 이미 연산 2로 수행한 수라면(!visited[tmp[0])라면 패스

제대로 풀이방법이 떠오르지 않았다. 비슷한 문제를 푼적이 있는데 DP로 푸는방법이 훨씬 간단했던것같다.

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

[난이도]

- Silver 3

[알고리즘]

- bfs

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static int[][] graph;
    static boolean[] visited;
    static int n,m, answer = 0;


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        graph = new int[n + 1][n + 1]; // 0부터 시작이 아닌 1부터 시작이기 때문 n + 1
        visited = new boolean[n + 1];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            graph[u][v] = graph[v][u] = 1; // 양방향간선
        }

        bfs();
        System.out.println(answer);


    }
    static void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1); // 1부터 시작
        visited[1] = true; // 방문한 곳은 true
        while (!queue.isEmpty()) {
            int tmp = queue.poll();
            for (int i = 1; i <= n; i++) {
                if (graph[tmp][i] == 1 && !visited[i]) { // 현재번호와 연결된곳이면서 방문하지 않은 장소
                    queue.offer(i);
                    visited[i] = true;
                    answer ++;
                }
            }
        }
    }
}

[풀이]

1. 큐에 1을 담는다. (1번과 연결된것을 찾기 위함)

2. 큐에 담긴 번호와 연결된 노드이면서 방문하지않은 노드일 경우 큐에 연결된 노드를 담는다.

3. 큐가 빌때까지 반복한다.