'dfs' 태그의 글 목록

dfs

[BOJ] 3197 백조의 호수 (Java)

1. 문제요약

3197번: 백조의 호수

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

www.acmicpc.net

R x C 직사각형 모양의 호수가 존재한다. 이 호수에는 백조가 두 마리 존재하는데 빙판이 있어 서로 만날 수 없다. 하루가 지날 때마다 물에 인접한 빙판들은 모두 녹는다고 할 때 며칠이 지나야 백조 두 마리가 만날 수 있는지 구하시오.

2. 문제예제

3. 문제풀이(수동)

전형적인 BFS 문제로 수동 풀이는 진행하지 않는다. 지문에서 언급한 내용처럼 물에 인접한 빙판들은 모두 녹는다.

녹을 때 두 백조가 만날 수 있는지만 체크하면 된다.

4. 팩트추출

Fact 1 : 전형적인 BFS 문제이다. 한 번 맵을 훑으면서 빙판을 녹이고, 백조가 서로 만나는지 다시 맵을 훑으면 된다. 단순 BFS 구현 문제라고 생각이 들지만, R 과 C 가 무려 1500 으로 한 번 맵을 탐색할 때마다 1500 * 1500 시간복잡도가 발생한다. 그것도 빙판을 녹일 때 한 번, 백조가 서로 만나는지 확인하기 위해 한 번 수행하면 총 1500 * 1500 * 2 시간복잡도가 된다. 조금 더 효과적으로 BFS 를 수행해야 한다.

Fact 2 : 백조 중심으로 BFS 를 수행하면 빙판을 만나거나 백조를 만나거나 두 가지 경우를 만나게 된다. 백조를 만나면 그 동안에 계산된 day 를 리턴하면 되고, 빙판을 만났다면 그 빙판들을 기억하기 위해 모두 큐에 담아 그 큐에서부터 다시 시작하면 된다. 빙판을 녹이기 위한 BFS 는 따로 수행해서 서로 영향을 미치지 않게 동작시킨다. 따라서, Water 에 대한 큐, 다음 검색을 위한 큐가 필요하다.

5. 문제전략

문제 전략은 팩트 추출을 통해 알아보았다. 백조 중 하나부터 시작해서 dfs 를 수행하고 빙판을 만나면 그 지점들을 기억했다가 다시 그 부분부터 dfs 를 시작하면 된다. 다시 dfs 를 시작하기 전 빙판이 녹아야 하므로 빙판에 대한 dfs 를 한 번 수행한다.

6. 소스코드

package org.example;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int R, C;
    private static Node[] swan;
    private static char[][] map;
    private static Queue<Node> queue, waterQueue;
    private static boolean[][] visited;
    private static final int[] dr = { -1, 1, 0, 0 };
    private static final int[] dc = { 0, 0, -1, 1 };
    private static int day = 0;
    static class Node {
        int r, c;
        Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
    private static void waterBFS() {
        // 한 번만 녹여야 하므로, 현재 큐 사이즈만큼만 돌린다.
        int waterSize = waterQueue.size();
        while (waterSize-- > 0) {
            Node now = waterQueue.poll();
            for (int i = 0; i < 4; i++) {
                int nextR = now.r + dr[i];
                int nextC = now.c + dc[i];
                if (nextR >= R || nextR < 0 || nextC >= C || nextC < 0) continue;
                if (map[nextR][nextC] == 'X') {
                    map[nextR][nextC] = '.';
                    waterQueue.offer(new Node(nextR, nextC));
                }
            }
        }
    }
    private static void BFS() {
        boolean meet = false;
        while (true) {
            Queue<Node> nextQueue = new LinkedList<>();
            while (!queue.isEmpty()) {
                Node now = queue.poll();
                if (now.r == swan[1].r && now.c == swan[1].c) {
                    meet = true;
                    break;
                }
                for (int i = 0; i < 4; i++) {
                    int nextR = now.r + dr[i];
                    int nextC = now.c + dc[i];
                    if (nextR >= R || nextR < 0 || nextC >= C || nextC < 0 || visited[nextR][nextC]) continue;
                    visited[nextR][nextC] = true;
                    if (map[nextR][nextC] == 'X') {
                        nextQueue.offer(new Node(nextR, nextC));
                        continue;
                    }
                    queue.offer(new Node(nextR, nextC));
                }
            }
            if (meet) break;
            queue = nextQueue;
            waterBFS();
            day++;
        }
        return;
    }

    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new char[R][C];
        swan = new Node[2];
        queue = new LinkedList<>();
        waterQueue = new LinkedList<>();
        visited = new boolean[R][C];

        int swanIndex = 0;
        for (int i = 0; i < R; i++) {
            char[] line = br.readLine().toCharArray();
            for (int j = 0; j < C; j++) {
                map[i][j] = line[j];
                if(map[i][j] == 'L') {
                    swan[swanIndex++] = new Node(i, j);
                }
                if(map[i][j] != 'X') {
                    waterQueue.offer(new Node(i, j));
                }
            }
        }
        queue.offer(swan[0]);
        visited[swan[0].r][swan[0].c] = true;
        BFS();
        System.out.println(day);
    }
}

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 9376 탈옥 (Java) (0)	2022.10.02
[BOJ] 이항 계수 (Java) (0)	2022.09.29
[BOJ] 1655 가운데를 말해요 (Java) (0)	2022.09.28
[BOJ] 12865 평범한 배낭 (Java) (0)	2022.09.27
[BOJ] N과 M (Java) (0)	2022.09.27

[BOJ] N과 M (Java)

[문제 개요]

N 개의 자연수에서 M 개를 고른 수열을 출력하시오.

각 문제마다 조건이 추가된다. 이 N 과 M 시리즈는 재귀함수(DFS)의 본질을 이해하고, 우리가 흔히 접할 수 있는 순열 및 조합 문제를 풀 수 있는 기초가 되기 때문에 꼭 풀어보는 것을 권장한다.

N과 M (1)

+ 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

+ 자기 자신은 제외하고 남은 수열을 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int N, M;
    private static int[] combinations;
    private static boolean[] visited;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                combinations[depth] = i + 1;
                visited[i] = true;
                dfs(i, depth + 1);
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        combinations = new int[N];
        visited = new boolean[N];
        dfs(0,0);
        System.out.println(sb.toString());
    }
}

N과 M (2)

+ 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int N, M;
    private static int[] combinations;
    private static boolean[] visited;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = index; i < N; i++) {
            if (!visited[i]) {
                combinations[depth] = i + 1;
                visited[i] = true;
                dfs(i, depth + 1);
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        combinations = new int[N];
        visited = new boolean[N];
        dfs(0,0);
        System.out.println(sb.toString());
    }
}

N과 M (3)

+ 1부터 N까지 자연수 중에서 M개를 고른 수열

+ 같은 수를 여러 번 골라도 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int N, M;
    private static int[] combinations;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 0; i < N; i++) {
            combinations[depth] = i+1;
            dfs(i, depth + 1);
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        combinations = new int[N];
        dfs(0,0);
        System.out.println(sb.toString());
    }
}

N과 M (4)

+ 1부터 N까지 자연수 중에서 M개를 고른 수열

+ 같은 수를 여러 번 골라도 된다.

+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int N, M;
    private static int[] combinations;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = index; i < N; i++) {
            combinations[depth] = i+1;
            dfs(i, depth + 1);
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        combinations = new int[N];
        dfs(0,0);
        System.out.println(sb.toString());
    }
}

N과 M (5)

+ 자기 자신은 제외하고 남은 수열을 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int N, M;
    private static int[] combinations, items;
    private static boolean[] visited;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 0; i < N; i++) {
            if(!visited[i]) {
                combinations[depth] = items[i];
                visited[i] = true;
                dfs(i, depth + 1);
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        items = new int[N];
        combinations = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            items[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(items);
        visited = new boolean[N];
        dfs(0,0);
        System.out.println(sb.toString());
    }
}

N과 M (6)

+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int N, M;
    private static int[] combinations, items;
    private static boolean[] visited;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = index; i < N; i++) {
            if(!visited[i]) {
                combinations[depth] = items[i];
                visited[i] = true;
                dfs(i, depth + 1);
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        items = new int[N];
        combinations = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            items[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(items);
        visited = new boolean[N];
        dfs(0,0);
        System.out.println(sb.toString());
    }
}

N과 M (7)

+ 같은 수를 여러 번 골라도 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int N, M;
    private static int[] combinations, items;
    private static boolean[] visited;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 0; i < N; i++) {
            combinations[depth] = items[i];
            dfs(i,depth + 1);
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        items = new int[N];
        combinations = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            items[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(items);
        dfs(0,0);
        System.out.println(sb.toString());
    }
}

N과 M (8)

+ 같은 수를 여러 번 골라도 된다.

+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int N, M;
    private static int[] combinations, items;
    private static boolean[] visited;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = index; i < N; i++) {
            combinations[depth] = items[i];
            dfs(i,depth + 1);
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        items = new int[N];
        combinations = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            items[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(items);
        dfs(0,0);
        System.out.println(sb.toString());
    }
}

N과 M (9)

+ 중복 수열은 출력하지 않는다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int N, M;
    private static int[] combinations, items;
    private static boolean[] visited;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        int prevNumber = -1;
        for (int i = 0; i < N; i++) {
            if (prevNumber != items[i] && !visited[i]) {
                combinations[depth] = items[i];
                prevNumber = items[i];
                visited[i] = true;
                dfs(depth + 1);
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        items = new int[N];
        combinations = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            items[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(items);
        visited = new boolean[N];
        dfs(0);
        System.out.println(sb.toString());
    }
}

N과 M (10)

+ 같은 수를 여러 번 골라도 된다.

+ 중복 수열은 출력하지 않는다.

+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int N, M;
    private static int[] combinations, items;
    private static boolean[] visited;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        int prevNumber = -1;
        for (int i = index; i < N; i++) {
            if (prevNumber != items[i] && !visited[i]) {
                combinations[depth] = items[i];
                prevNumber = items[i];
                visited[i] = true;
                dfs(i, depth + 1);
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        items = new int[N];
        combinations = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            items[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(items);
        visited = new boolean[N];
        dfs(0, 0);
        System.out.println(sb.toString());
    }
}

N과 M (11)

+ 같은 수를 여러 번 골라도 된다.

+ 중복 수열은 출력하지 않는다.

+ 같은 숫자를 여러 번 골라도 된다.

package org.example;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int N, M;
    private static int[] combinations, items;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        int prevNumber = -1;
        for (int i = 0; i < N; i++) {
            if (prevNumber != items[i]) {
                combinations[depth] = items[i];
                prevNumber = items[i];
                dfs(i, depth + 1);
            }
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        items = new int[N];
        combinations = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            items[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(items);
        dfs(0, 0);
        System.out.println(sb.toString());
    }
}

N과 M (12)

+ 같은 수를 여러 번 골라도 된다.

+ 중복 수열은 출력하지 않는다.

+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int N, M;
    private static int[] combinations, items;
    private static List<Integer> itemsDistinct;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        int prevNumber = -1;
        for (int i = index; i < N; i++) {
            if (prevNumber != items[i]) {
                combinations[depth] = items[i];
                prevNumber = items[i];
                dfs(i, depth + 1);
            }
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        items = new int[N];
        combinations = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            items[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(items);
        dfs(0, 0);
        System.out.println(sb.toString());
    }
}

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 1655 가운데를 말해요 (Java) (0)	2022.09.28
[BOJ] 12865 평범한 배낭 (Java) (0)	2022.09.27
[BOJ] 11658 구간 합 구하기 3 (0)	2022.08.31
[BOJ] 1520 내리막 길 (1)	2022.08.31
[BOJ] 10999 구간 합 구하기 2 (0)	2022.08.30

[BOJ] 1520 내리막 길

1. 문제요약

1520번: 내리막 길 (acmicpc.net)

1520번: 내리막 길

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

www.acmicpc.net

지도의 각 칸에는 그 지점의 높이가 주어지며 (0, 0) 지점에서 (n-1, m-1) 지점으로 내려가려고 한다. 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 할 때 이동할 수 있는 경로의 수를 구하시오.

2. 문제예제

3. 팩트추출

Fact 1 : 전형적인 BFS 와 DFS 문제인 것처럼 보이지만, 입력의 범위를 보면 완전 탐색 시 시간 초과가 발생할 수 있다. 최대 칸 수가 500 * 500 으로 250000 이며 상하좌우 4방향으로 움직일 수 있으니 4 의 250000 제곱 경우의 수가 존재한다. 경우의 수를 줄일 수 있는 방법을 찾아야 한다.

Fact 2 : 문제 예제를 살펴보면 전체 문제의 답이 작은 부분 문제의 답의 합으로 구성되어 있다. 50 번 지점에서 목적지까지 가는 경로의 수는 45번 지점에서 가는 경로의 수 + 35번 지점에서 가는 경로의 수로 이루어져 있다. 35번 지점이나 30번 지점, 27번 지점은 경로의 수가 하나로 나중에 이 지점을 방문하더라도 계산할 필요가 없다. 즉 DP 문제이다.

Fact 3 : 기존 DFS 나 BFS 에서 사용하던 visited 배열을 응용하여 "해당 지점에서 목적지까지 가는 경로의 수" 로 생각하여 해당 값을 재활용하면 탐색 범위를 줄일 수 있다. 여기서 중요한 점은 DFS 와 BFS 의 visited 배열 활용도가 조금 다르다는 것이다. BFS 는 주변부터 탐색하기 때문에 단순 방문했는지 여부만 파악할 수 있지만 DFS 는 한 가지 경우의 수부터 모두 탐색하고 다시 원래 위치로 돌아오기 때문에 수행 도중 visited 배열을 오염시킨다면 그 경로는 다시 탐색하지 않아도 된다. 4 번 문제 풀이 (수동) 부분에서 자세히 확인한다.

Fact 4 : DP[x][y] 배열을 0 으로 초기화하면 이 경로의 수가 0 인지 노드를 방문하지 않은 것인지 확인이 불가능하다. DP 배열이 visited 배열의 역할도 하기 때문에 -1 로 초기화한다.

4. 문제풀이(수동)

문제 예제 입력 1을 DFS 알고리즘 + DP 방식으로 문제를 풀었을 때 애니메이션이다.

손수 애니메이션으로 만들어준 우투리와툴툴 티스토리 블로그님께 감사의 말씀을 전한다. 덕분에 이해하기가 쉽다.

5. 문제전략

문제 전략은 팩트 추출을 통해 알아보았다. DFS + DP 방식으로 문제를 풀었다.

6. 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int M, N;
    static int[][] map;
    static int[][] dp;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, 1, -1 };
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        map = new int[M][N];
        dp = new int[M][N];

        for(int j = 0; j < M; j++) {
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                map[j][i] = Integer.parseInt(st.nextToken());
            }
        }
        initDP();
        System.out.println(dfs(0, 0));
    }
    private static void initDP() {
        for(int j = 0; j < M; j++) {
            for (int i = 0; i < N; i++) {
                dp[j][i] = -1;
            }
        }
    }
    private static int dfs(int x, int y) {
        if(x == M-1 && y == N-1){ return 1; }
        if(dp[x][y] != -1) return dp[x][y];

        dp[x][y] = 0;
        for (int i=0; i<4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];

            if (newX < 0 || newX >= M || newY < 0 || newY >= N) continue;
            if (map[x][y] <= map[newX][newY]) continue;

            dp[x][y] += dfs(newX, newY);
        }
        return dp[x][y];
    }
}

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] N과 M (Java) (0)	2022.09.27
[BOJ] 11658 구간 합 구하기 3 (0)	2022.08.31
[BOJ] 10999 구간 합 구하기 2 (0)	2022.08.30
[BOJ] 9426 중앙값 측정 (0)	2022.08.19
[BOJ] 2138 전구와 스위치 (0)	2022.08.17

[알고리즘] BFS & DFS

BFS 알고리즘은 넓이 우선 탐색 알고리즘이며, DFS 알고리즘은 깊이 우선 탐색 알고리즘이다.

<템플릿>

public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        // 현재 노드를 방문 처리
        visited[start] = true;
        // 큐가 빌 때까지 반복
        while(!q.isEmpty()) {
            // 큐에서 하나의 원소를 뽑아 출력
            int x = q.poll();
            // 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
            for(int i = 0; i < graph.get(x).size(); i++) {
                int y = graph.get(x).get(i);
			  // if 제어문의 반복
			  // if(visited[y]) continue;
                q.offer(y);
                visited[y] = true;
            }
        }
    }

public static void dfs(int x) {
        // 현재 노드를 방문 처리
        visited[x] = true;
        System.out.print(x + " ");
        // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for (int i = 0; i < graph.get(x).size(); i++) {
            int y = graph.get(x).get(i);
            if (!visited[y]) dfs(y);
        }
    }

'알고리즘 > 개념' 카테고리의 다른 글

[알고리즘] Segment Tree (0)	2022.08.29
[알고리즘] 투 포인터 알고리즘 (Two Pointer) (0)	2022.06.29
[알고리즘] LCA (Lowest Common Ancestor) (0)	2022.05.04
[알고리즘] DP (Dynamic Programming) (0)	2021.05.10

PREV 1 NEXT

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

골드에그

dfs

[BOJ] 3197 백조의 호수 (Java)

1. 문제요약

2. 문제예제

3. 문제풀이(수동)

4. 팩트추출

5. 문제전략

6. 소스코드

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] N과 M (Java)

[문제 개요]

N과 M (1)

N과 M (2)

N과 M (3)

N과 M (4)

N과 M (5)

N과 M (6)

N과 M (7)

N과 M (8)

N과 M (9)

N과 M (10)

N과 M (11)

N과 M (12)

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 1520 내리막 길

1. 문제요약

2. 문제예제

3. 팩트추출

4. 문제풀이(수동)

5. 문제전략

6. 소스코드

'알고리즘 > BOJ' 카테고리의 다른 글

[알고리즘] BFS & DFS

'알고리즘 > 개념' 카테고리의 다른 글

+ Recent posts

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역