지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력


지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

 

출력


각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

 

 

풀이


public class Main {
    static int N, M, x, y;
    static int[][] field;
    static boolean[][] visited;
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        field = new int[N][M];
        visited = new boolean[N][M];
        for (int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<M; j++){
                int num = Integer.parseInt(st.nextToken());
                field[i][j] = num;
                if (num == 2){
                    x = i;
                    y = j;
                }
            }
        }
        field[x][y] = 0;
        BFS(x, y);
        for (int i=0; i<N; i++){
            for (int j=0; j<M; j++){
                if (!visited[i][j] && field[i][j] != 0){
                    field[i][j] = -1;
                }
                sb.append(field[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
    static void BFS(int x, int y){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()){
            int[] now = queue.poll();
            for (int i=0; i<4; i++){
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if (nx >= 0 && ny >= 0 && nx < N && ny < M){
                    if (!visited[nx][ny] && field[nx][ny] > 0){
                        visited[nx][ny] = true;
                        queue.offer(new int[]{nx, ny});
                        field[nx][ny] = field[now[0]][now[1]] + 1;
                    }
                }
            }
        }

    }

}

 

해설


https://choincnp.tistory.com/92

 

[백준/2178] - 미로 탐색(JAVA)

N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할

choincnp.tistory.com

미로 탐색 문제보다 조금 더 어려운 BFS 문제다.

그러나 미로 탐색과 코드 자체는 동일하다.

static int N, M, x, y;
static int[][] field;
static boolean[][] visited;
static int[] dx = {0,0,-1,1};
static int[] dy = {1,-1,0,0};

시작점이 주어져 있지 않기 때문에, 배열의 크기와 시작점을 선언해놓고, 나머지 field와 visited, 그리고 가로 세로 이동을 고려한 델타 배열을 선언한다.

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        field = new int[N][M];
        visited = new boolean[N][M];
        for (int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<M; j++){
                int num = Integer.parseInt(st.nextToken());
                field[i][j] = num;
                if (num == 2){
                    x = i;
                    y = j;
                }
            }
        }
        field[x][y] = 0;
        BFS(x, y);
        for (int i=0; i<N; i++){
            for (int j=0; j<M; j++){
                if (!visited[i][j] && field[i][j] != 0){
                    field[i][j] = -1;
                }
                sb.append(field[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }

메인스택 자체는 어렵지 않다.

다만 필드를 고려할 때 시작점이 어디에 주어질 지 모르므로 필드값을 계산하여 스타팅 포인트가 2일경우 그때의 좌표값을 저장해야 한다.

그리고 field[x][y]가 2로 시작하면, 이를 읽어들이면서 BFS 필드에 저장을 하기 때문에 모든 거리 수가 +2로 계산된다.

물론 다른 2차배열을 선언해주어도 되지만, 메모리 절약을 위해 시작값을 0으로 잡아준다.(field[x][y] = 0)

 

그리고 BFS를 돌리는데, 여기서 바로 필드값을 출력하면 안 된다.

문제의 조건에 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다. 가 있기 때문이다.

개인적으로 그냥 기계적으로 문제를 풀다가 저 문장을 보지 못하고 계속 '왜 틀렸지?'를 생각했는데

조건을 잘 봐야 한다. 그래서 다음과 같은 조건을 생각했다.

'원래 갈 수 있는데 가지 못한 부분 = 방문하지는 못했지만 필드값이 0이 아닌 부분'

으로 해석하였고, 이 조건을 넣어주고 출력하였다.

static void BFS(int x, int y){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()){
            int[] now = queue.poll();
            for (int i=0; i<4; i++){
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if (nx >= 0 && ny >= 0 && nx < N && ny < M){
                    if (!visited[nx][ny] && field[nx][ny] > 0){
                        visited[nx][ny] = true;
                        queue.offer(new int[]{nx, ny});
                        field[nx][ny] = field[now[0]][now[1]] + 1;
                    }
                }
            }
        }

    }

BFS 함수 자체가 어려운 것은 아니다. 아까 링크했던 미로탐색 문제와 완전히 동일하다.

큐를 선언하는것부터 시작하는데, 큐에 집어넣을 노드는 int형 배열이 되어야 한다.

방문 배열에 추가해주고, 큐가 빌 때까지 계속 뽑아낸다.

델타 배열을 방문하면서 방문하지 않았고 배열값이 0이 아닌 노드에 한해서

방문 배열을 체크해주고, 지나온 값에 이전까지의 뎁스를 기록한다.

마지막으로 새로운 좌표를 다시 큐에 추가해주고 계속 while문을 돌리면 된다.

 

BFS의 원리 자체만 이해했다면 크게 어렵지는 않은 문제다.

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

[백준/7576] - 토마토(JAVA)  (0) 2023.09.19
[백준/1697] - 숨바꼭질(JAVA)  (0) 2023.09.18
[백준/2178] - 미로 탐색(JAVA)  (0) 2023.09.17
[백준/1260] - DFS와 BFS(JAVA)  (0) 2023.09.17
[백준/1526] - 내리막길(JAVA)  (0) 2023.09.15

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력


첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

 

출력


첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

풀이


public class Main {
    static int N, M;
    static int[][] field;
    static boolean[][] visited;
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        field = new int[N][M];
        visited = new boolean[N][M];
        for (int i=0; i<N; i++){
            String row = br.readLine();
            for (int j=0; j<M; j++){
                field[i][j] = row.charAt(j)-48;
            }
        }
        BFS(0,0);
        System.out.println(field[N-1][M-1]);
    }
    static void BFS(int x, int y){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;
        while (!queue.isEmpty()){
            int[] now = queue.poll();
            for (int i=0; i<4; i++){
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if (nx >=0 && ny >= 0 && nx < N && ny < M){
                    if (!visited[nx][ny] && field[nx][ny] != 0){
                        visited[nx][ny] = true;
                        field[nx][ny] = field[now[0]][now[1]] + 1;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
        }
    }
}

해설


전형적인 BFS문제다. 완전탐색하며 몇번째 뎁스에서 원하는 값을 찾을 수 있는지를 확인하는 문제다.

최단거리를 구하는 것이 왜 BFS가 유리한지, BFS가 왜 '너비 우선 탐색'인지를 알 수 있는 좋은 문제다.

DFS는 일단 가면서 탐색하여 시간초과를 일으키지만 BFS는 해당 깊이에서 갈 수 있는 노드를 탐색하고 가기 때문에 최단거리 문제 풀이에 조금 더 용이하다.

먼저 DFS의 진행 상황을 분석하고 풀이로 넘어간다.

4 6
110110
110110
111111
111101

 

위의 예제를 depth를 따라가보자.

모든 '뎁스를 탐색하는 과정'에서 탐색했으면 좌표 안에 최단거리를 집어넣어줘야 한다.

 

depth1

(0,0)을 확인하고 방문 배열을 체크한 다음, 상하좌우를 확인하면서 막혀있지 않고, 숫자가 1이라면 그 좌표를 새로 큐에 추가한다. 새로 추가한 좌표는 방문 배열에 미리 체크해놓는다.

현재 큐 = [[1,0], [0,1]]

depth 2

  • (1,0)을 확인하고, 상하좌우를 확인하고 조건에 맞는 (1,1)좌표를 큐에 추가하고 방문 배열에 (1,1)을 체크한다.
  • (0,1)을 확인하고, 상하좌우를 확인하고 조건에 맞는 (0,2)좌표를 큐에 추가한다. (1,1)은 이미 방문 배열에 있으므로 추가하지 않는다.

현재 큐 = [[1,1], [2,1]]

depth 3

  • (1,1)을 확인하고, 상하좌우를 확인한 뒤 조건에 맞는 (2,1)좌표를 큐에 추가하고 방문 배열을 체크한다.
  • (0,2)을 확인하고, 상화좌우를 확인한 뒤 조건에 맞는 (0,3)좌표를 큐에 추가하고 방문 배열을 체크한다.

현재 큐 = [[2,1], [0,3]]

 

이런식으로 depth를 하나씩 늘려서 진행한다.

결국 마지막에 배열은 다음과 같이 변한다.

1 2 0 8 9 0
2 3 0 7 8 0
3 4 5 6 7 8
4 5 6 7 0 9

각 배열의 값은, 이 배열까지 오기 위한 depth의 최소값을 띄게 된다.

 

이제, 코드를 살펴보자.

    static int N, M;
    static int[][] field;
    static boolean[][] visited;
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};

특이사항 없이 가로, 세로를 받을 N, M과 배열을 받고 뎁스를 기록할 field, 방문 기록용 visited 배열과 델타 배열을 선언한다.

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        field = new int[N][M];
        visited = new boolean[N][M];
        for (int i=0; i<N; i++){
            String row = br.readLine();
            for (int j=0; j<M; j++){
                field[i][j] = row.charAt(j)-48;
            }
        }
        BFS(0,0);
        System.out.println(field[N-1][M-1]);
    }

field배열을 채우고, (0,0)에서 BFS를 시작하고 맨 마지막에 도착지의 depth를 출력하면 된다.

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

가장 중요한 BFS 함수다

큐를 선언하는것부터 시작하는데, 큐에 집어넣을 노드는 int형 배열이 되어야 한다.

방문 배열에 추가해주고, 큐가 빌 때까지 계속 뽑아낸다.

델타 배열을 방문하면서 방문하지 않았고 배열값이 0이 아닌 노드에 한해서

방문 배열을 체크해주고, 지나온 값에 이전까지의 뎁스를 기록한다.

마지막으로 새로운 좌표를 다시 큐에 추가해주고 계속 while문을 돌리면 된다.

 

어렵지는 않았으나, 처음 BFS 문제를 풀 때에는 조금 어려운 감이 있다.

그러나 BFS의 원리를 알고 원리대로 프로그래밍을 풀어간다면 코드 자체는 어렵지 않다.

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

[백준/1697] - 숨바꼭질(JAVA)  (0) 2023.09.18
[백준/14940] - 쉬운 최단거리(JAVA)  (0) 2023.09.17
[백준/1260] - DFS와 BFS(JAVA)  (0) 2023.09.17
[백준/1526] - 내리막길(JAVA)  (0) 2023.09.15
[백준/1987] - 알파벳(JAVA)  (0) 2023.09.15

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력


첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력


첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

 

풀이


public class bojtest {
    static int N, M, V;

    static ArrayList<Integer>[] arr;

    static boolean[] visited;

    static StringBuilder sb = new StringBuilder();


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());
        arr = new ArrayList[N+1];
        visited = new boolean[N+1];
        for (int i=1; i<=N; i++){
           arr[i] = new ArrayList<>();
        }
        for (int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            arr[s].add(e);
            arr[e].add(s);
        }
        for (int i=1; i<=N; i++){
            Collections.sort(arr[i]);
        }
        DFS(V);
        sb.append("\n");
        visited = new boolean[N+1];
        BFS(V);
        System.out.println(sb.toString());
    }
    static void DFS(int x){
        sb.append(x).append(" ");
        visited[x] = true;
        for (int i : arr[x]){
            if (!visited[i]){
                DFS(i);
            }
        }
    }

    static void BFS(int x){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);
        visited[x] = true;

        while (!queue.isEmpty()){
            int i = queue.poll();
            sb.append(i).append(" ");
            for (int n : arr[i]){
                if (!visited[n]){
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}

해설


BFS와 DFS를 비교하는 문제였다.

단순히 DFS와 BFS를 돌리는 문제보다도, DFS와 BFS가 어떻게 실행되는지를 이해하고 언제 사용할 것인지를 파악하는데 도움이 되는 문제이다.

하나하나 천천히 코드를 뜯어보자.

static int N, M, V;
static ArrayList<Integer>[] arr;
static boolean[] visited;
static StringBuilder sb = new StringBuilder();

처음 선언해줄 변수들은 DFS에서 했던 그대로 가로, 세로, 그리고 target number와

노드의 연결고리를 기록할 ArrayList 배열, 그리고 방문 배열이 필요하다.

 

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());
        arr = new ArrayList[N+1];
        visited = new boolean[N+1];
        for (int i=1; i<=N; i++){
           arr[i] = new ArrayList<>();
        }
        for (int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            arr[s].add(e);
            arr[e].add(s);
        }
        for (int i=1; i<=N; i++){
            Collections.sort(arr[i]);
        }
        DFS(V);
        sb.append("\n");
        visited = new boolean[N+1];
        BFS(V);
        System.out.println(sb.toString());
    }

메인 스택은 3부분으로 나눌 수 있다.

1.DFS/BFS 실행을 위해 arr과 방문 배열을 선언하고 초기화하는 것, 시작과 끝 노드를 이어주는 것

2.문제에 적힌 대로 '정점 번호가 낮은 것을 먼저 선행'하기 위해 소팅을 하는것

3.DFS를 실행하고, 방문 배열을 초기화시킨 뒤 BFS를 실행하고 출력하는 것

static void DFS(int x){
        sb.append(x).append(" ");
        visited[x] = true;
        for (int i : arr[x]){
            if (!visited[i]){
                DFS(i);
            }
        }
    }

    static void BFS(int x){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);
        visited[x] = true;

        while (!queue.isEmpty()){
            int i = queue.poll();
            sb.append(i).append(" ");
            for (int n : arr[i]){
                if (!visited[n]){
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

DFS와 BFS 실행이다.

DFS는 실행 번호를 적어준 뒤 방문하지 않았던 노드를 토대로 방문하는 로직이다.

BFS는 Queue를 선언하고, 큐에 노드를 넣어주는 것부터 시작된다.

다음 예를 보자.

4 5 1
1 2
1 3
1 4
2 4
3 4

<DFS 실행순서>

DFS(1)을 실행한다. arr[1]에는 2, 3이 들어있으므로 1번 방문을 체크하고 DFS(2)를 실행한다.

DFS(2)을 실행한다. arr[2]에는 4가 들어있으므로 2번 방문을 체크하고 DFS(4)를 실행한다.

DFS(4)를 실행한다. arr[4]에는 아무것도 들어있지 않으므로 4번 방문을 체크하고 스택을 종료한다.

다시 1번으로 돌아가서, 스택에 쌓여 있는 DFS(3)을 실행한다.

DFS(3)을 실행한다. arr[3]에는 4가 들어있지만 방문하였으므로 그냥 종료한다.

<BFS 실행순서>

타겟 넘버가 1일경우 1을 큐에 넣는다.

현재 큐 상태 : [1]

그리고 큐에서 다시 1을 뽑아서, 1과 연결된 노드들을 다시 큐에 넣는다. 1번 방문은 체크한다.

위의 예제에서라면 2와 3을 큐에 넣을 것이다.

큐는 FIFO 구조로 돌아가니까, 2와 3을 큐에 넣을 것이다. 2와 3번 방문은 체크한다.

현재 큐 상태 : [2 3]

빈 큐가 아니므로, poll을 하면 2번 노드가 빠진다. 2번 배열에 있는 4번 노드가 queue에 추가된다. 4번 방문은 체크한다.

현재 큐 상태 : [3 4]

빈 큐가 아니므로, poll을 하면 3번 노드가 빠진다. 3번 배열에 있는 4번 노드가 queue에 추가되어야 하나, 방문 배열에 체크되어있기 때문에 넘어간다.

현재 큐 상태 : [4]

빈 큐가 아니므로, poll을 하면 4번 노드가 빠진다. 4번 배열은 연결되어있는 노드가 없으므로 BFS를 끝낸다.

 

 

위의 예제를 기준으로, 실행순서가 DFS는 1 2 4 3이 나오고 BFS는 1 2 3 4가 나온다.

스택을 기준으로 실행하는 DFS이냐, 큐를 기준으로 실행하는 BFS이냐는 문제를 점점 풀어가며 감을 익혀가야겠지만,

한가지는 알 수 있다. BFS는 최단거리를 찾는데 유용하고, DFS는 브루트 포스같이 모든 경로를 찾는 데에 유용하다.

 

 

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

 

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

입력


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

 

출력


첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

 

풀이


public class Main {

    static int N, M;
    static int[][] field;

    static int[][] dp;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        field = new int[N][M];
        dp = new int[N][M];
        for (int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<M; j++){
                field[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;
            }
        }
        //DFS
        System.out.println(DFS(0,0));
    }
    static int DFS(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 + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx <N && ny < M){
                if (field[nx][ny] < field[x][y]){
                    dp[x][y] += DFS(nx, ny);
                }
            }
        }

        return dp[x][y];
    }
}

해설


https://choincnp.tistory.com/88

 

[백준/1987] - 알파벳(JAVA)

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으

choincnp.tistory.com

알파벳 문제가 DFS+DP의 맛보기라면, 이번 내리막길 문제는 본격적으로 DFS+DP를 이용하는 문제이다.

물론 DFS만 이용해서 문제를 풀 수도 있다. 그러나 문제는 시간 초과가 발생한다.

가로와 세로가 500x500까지 주어질 수 있어서, 모든 루트를 다 거쳐갈때 5초라는 시간이 발생하지만 시간 제한은 2초이기 때문이다.

<DFS만을 이용한 풀이법>

 

public class Main {

    static int N, M, answer;
    static int[][] field;
    static boolean[][] visited;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        field = new int[N][M];
        visited = new boolean[N][M];
        for (int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<M; j++){
                field[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //DFS
        DFS(0,0,field[0][0]);

        System.out.println(answer);
    }
    static void DFS(int x, int y, int number){
        if (x == N-1 && y == M-1){
            answer++;
        }
        visited[x][y] = true;
        for (int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx <N && ny < M){
                if (!visited[nx][ny] && field[nx][ny] < number){
                    DFS(nx, ny, field[nx][ny]);
                }
            }
        }
        visited[x][y] = false;
    }
}

그럼 지금부터 DP의 Top-down 방식을 이용한 풀이를 해 보자.

static int N, M;
static int[][] field;
static int[][] dp;
static int[] dx = {0,0,1,-1};
static int[] dy = {1,-1,0,0};

먼저, 가로와 세로 길이인 N, M을 선언하고, 값을 입력받을 field와 dp 배열을 선언한다.

마지막으로, 길은 상하좌우로 찾아나갈 것이므로 델타배열을 선언한다.

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        field = new int[N][M];
        dp = new int[N][M];
        for (int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<M; j++){
                field[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;
            }
        }
        //DFS
        System.out.println(DFS(0,0));
    }

메인스택 자체는 단순하다. 적절하게 변수를 초기화시켜주고,

int배열로 dp배열을 선언하였으므로, -1로 배열을 초기화해준다.

마지막으로 DFS함수만 print해주면 된다.

static int DFS(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 + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx <N && ny < M){
                if (field[nx][ny] < field[x][y]){
                    dp[x][y] += DFS(nx, ny);
                }
            }
        }

        return dp[x][y];
    }

DFS펑션이다. 

먼저 시작지점에서 끝지점까지 가는 방법의 수 자체를 출력해야 하므로, 끝 지점에 도달하였다면(x == N-1 && y == M-1)

1을 리턴하자.

최단 경로가 dp배열에 이미 기록되어있다면 바로 dp배열의 값을 리턴해준다.

마지막으로, 도달하였을경우 dp배열에 값을 0으로 바꿔주고(DFS에서 했던 visited와 비슷한 역할)

 

델타배열을 이용한 새 좌표를 구한 후 최소값으로 이동할 경우 dp배열에 DFS값을 더해준다.

만약 [x,y]발판 이후로 [N-1, M-1]까지의 경로가 존재할 경우 1이 더해질 것이고, 아니라면 아무 행동도 일어나지 않을 것이다.

Arrays.deepToString(dp) = [[3, 2, 2, 2, 1], [1, -1, -1, 1, 1], [1, -1, -1, 1, -1], [1, 1, 1, 1, -1]]

DFS를 실행시키고 난 다음 dp배열을 찍어보면 위와 같이 나온다.

이 dp배열의 뜻은 [x,y] -> [N-1, M-1]까지 가는 최단경로가 몇개나 나올 수 있을지를 찍는 배열이다.

DP는 아직 많이 학습하지 않았으므로, 나중에 따로 포스팅하겠다.

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력


첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

 

출력


첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

 

풀이


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

public class Main {

    static StringTokenizer st;
    static char[][] field;
    static boolean[] visited;
    static int R, C, count, max;

    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        field = new char[R][C];
        for (int i=0; i<R; i++){
            String row = br.readLine();
            for (int j=0; j<C; j++){
                field[i][j] = row.charAt(j);
            }
        }

        //DFS
        max = 1;
        visited = new boolean[26];
        count = 1;
        DFS(0,0,count);
        System.out.println(max);
    }
    static void DFS(int x, int y, int count) {
        visited[field[x][y]-65] = true;
        max = Math.max(max, count);
        for (int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < R && ny < C){
                if (!visited[field[nx][ny]-65]){
                    DFS(nx, ny, count+1);
                }
            }
        }
        visited[field[x][y]-65] = false;
    }
}

해설


'방문한 배열에 대해 어떻게 초기화를 적절히 해 줄 수 있을까'라는 구현이 가장 핵심인 DFS문제였다.

개인적으로 DP를 왜 사용하는 지에 대한 이유를 알 수 있는 문제라 중요하다고 생각했다.

[0,0]에서 [1,0]으로 이동할때와 [0,1]로 이동할때의 최댓값에 따라 이동하는데, visited 배열을 가만히 놔두면

기존 움직임에 대해서 다음 DFS가 체크할 수 없다.

static StringTokenizer st;
static char[][] field;
static boolean[] visited;
static int R, C, count, max;
static int[] dx = {0,0,-1,1};
static int[] dy = {1,-1,0,0};

방향을 체크해야 하니 델타배열을 생성하고, field와 visited를 만든다.

처음에는 visited와 alphabet이라는 배열을 두개 생성해서 visited와 alphabet에 대해 따로따로 체크했다.

그러나 alphabet 배열을 제거했고 이유는 다음과 같았다.

배열을 두 개 만든 이유는 방문했던 위치와 알파벳이 별개로 돌아갈거라고 생각했는데 그렇지 않았다

ㅇ예를 들어 다음 입력을 가정해보자.

2 4
CAAB
ACAB

C에서 [0,1]인 A로 이동했을 때, [1,1]인 C는 가면 안된다.

그러나 방문하지 않았던 배열이기 때문에 visited와 alphabet을 따로 만들었었는데

생각해보면 '방문했던 배열의 알파벳은 다시 밟지 않는다'의 원칙이 있기 때문에 visited가 곧 alphabet이 된다.

다만 visited배열을 알파벳 대문자와 같은 26개의 크기로 만들어주고, 밟을 때마다 알파벳에 체크를 해준다.

public class Main {

    static StringTokenizer st;
    static char[][] field;
    static boolean[] visited;
    static int R, C, count, max;

    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        field = new char[R][C];
        for (int i=0; i<R; i++){
            String row = br.readLine();
            for (int j=0; j<C; j++){
                field[i][j] = row.charAt(j);
            }
        }

        //DFS
        max = 1;
        visited = new boolean[26];
        count = 1;
        DFS(0,0,count);
        System.out.println(max);
    }

그래서 배열을 초기화하고 field에 값을 채운 뒤 DFS를 돌려준다.

    static void DFS(int x, int y, int count) {
        visited[field[x][y]-65] = true;
        max = Math.max(max, count);
        for (int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < R && ny < C){
                if (!visited[field[nx][ny]-65]){
                    DFS(nx, ny, count+1);
                }
            }
        }
        visited[field[x][y]-65] = false;
    }

가장 중요한 DFS 함수이다.

맨 마지막 줄에 visited를 false로 돌려놔야하는게 핵심이다.

아까의 input처럼 처음 C를 밟고 [1,0]에 있는 A를 밟았을때 visited를 체크하고 이걸 돌려놓지 않으면

[0,1]을 실행할 때 A를 밟지 못한다.

이것만 신경써서 풀어주면 쉬운 문제였다.

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력


첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력


첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

풀이


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

public class Main {

    static StringTokenizer st;
    static ArrayList<Integer>[] arr;
    static boolean[] visited;
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        arr = new ArrayList[T+1];
        parent = new int[T+1];
        visited = new boolean[T+1];
        for (int i = 1; i<T+1; i++){
            arr[i] = new ArrayList<>();
        }
        for (int i=0; i<T-1; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            arr[s].add(e);
            arr[e].add(s);
        }
        //DFS
        DFS(1);

        // 출력
        for (int i=2; i<T+1; i++){
            System.out.println(parent[i]);
        }
    }
    static void DFS(int x){
        visited[x] = true;
        for (int i : arr[x]){
            if (!visited[i]){
                parent[i] = x;
                DFS(i);
            }
        }
    }
}

해설


물론 전체적인 DFS 풀이의 기전은 비슷하지만, 여태까지 풀어본 DFS문제를 분류하라면, 크게 두개로 나눌 수 있다.

1. 전체 배열을 받아 연관관계를 찾고 영역의 개수 / 넓이를 찾는 문제

2. 일부 노드의 연관관계를 받아서 노드의 관계를 파악하는 문제

 

위의 문제는 2번에 속한다. 따라서 ArrayList<Integer>[] 배열을 이용함으로써 풀 수 있다.

    static StringTokenizer st;
    static ArrayList<Integer>[] arr;
    static boolean[] visited;
    static int[] parent;

그래서 ArrayList와 visited, 그리고 노드의 부모를 구해야 하므로 parent 배열을 선언한다.

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        arr = new ArrayList[T+1];
        parent = new int[T+1];
        visited = new boolean[T+1];
        for (int i = 1; i<T+1; i++){
            arr[i] = new ArrayList<>();
        }
        for (int i=0; i<T-1; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            arr[s].add(e);
            arr[e].add(s);
        }
        //DFS
        DFS(1);

        // 출력
        for (int i=2; i<T+1; i++){
            System.out.println(parent[i]);
        }
    }

ArrayList<Integer>[]같은 경우는 꼭 해줘야 할 것이, 선언한 후에 이를 초기화해주는 작업을 거쳐야 한다.

그리고 start와 end를 받아서 각 노드에 연결시켜준다.

예를 들어 4번 노드와 6번 노드가 연결되어 있다고 하면, 4번 노드에 6번을, 그리고 6번 노드에도 4번을 달아준다.

그리고 마지막으로 트리의 루트가 1이므로 DFS(1)을 실행시키고, 부모 노드의 리스트를 출력해주면 된다.

static void DFS(int x){
        visited[x] = true;
        for (int i : arr[x]){
            if (!visited[i]){
                parent[i] = x;
                DFS(i);
            }
        }
    }

DFS 함수같은 경우에는 각 ArrayList를 돌면서 방문하지 않았던 노드에 대해서 parent배열에 기입한다.

이 부분이 이해가 안 되는 사람이 있을 것이다. 예를 들면서 확인해보자.

7
1 6
6 3
3 5
4 1
2 4
4 7

1번 노드를 최상단 노드라고 하였으므로, 관계를 나타내면 다음과 같다.

1                                                                  
├─4──2
| └──7
└─6──3──5

DFS를 실행하기 전에 ArrayList의 내용을 찍어보면 다음과 같다.

for (ArrayList<Integer> i : arr){
 System.out.println("i = " + i);
}
===========
i = null
i = [6, 4]
i = [4]
i = [6, 5]
i = [1, 2, 7]
i = [3]
i = [1, 3]
i = [4]

이제 DFS를 실행했을 때의 경과를 보자.

DFS(1)을 실행하면 visited[1] 배열이 true로 바뀌고,

1번 배열의 [6, 4]에 대해서 재귀함수를 실행할 것인지를 물어본다.

6으로 넘어가서, 방문하지 않았으므로 방문했다는 체크를 하고 6의 parent는 1로 표기해놓는다.

그리고 DFS(6)을 실시한다. 6번 배열에는 [1,3]이 있고, 1은 표기했으므로 실행하지 않고 3번 노드로 넘어가서 3번 노드의 부모를 6으로 체크한다.

후의 노드에 대해서 전부 체크한다.

이런 식으로 흘러가는 간단한 ArrayList<Integer>[] 배열의 문제였다.

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

[백준/1260] - DFS와 BFS(JAVA)  (0) 2023.09.17
[백준/1526] - 내리막길(JAVA)  (0) 2023.09.15
[백준/1987] - 알파벳(JAVA)  (0) 2023.09.15
[백준/2468] - 안전 영역(JAVA)  (0) 2023.09.14
[백준/4963] - 섬의 개수(JAVA)  (2) 2023.09.14

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다.

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다).

또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다.

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다.

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

풀이

public class Main{

    static StringTokenizer st;

    static int[][] land;
    static boolean[][] visited;

    static int N, count;

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


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        land = new int[N][N];
        int maxHeight = 0;
        for (int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<N; j++){
                int h = Integer.parseInt(st.nextToken());
                land[i][j] = h;
                maxHeight = Math.max(maxHeight, h);
            }
        }
        int max = 0;
        //DFS
        for (int i=0; i<maxHeight; i++){
            count = 0;
            visited = new boolean[N][N];
            for (int j=0; j<N; j++){
                for (int k=0; k<N; k++){
                    if (!visited[j][k] && land[j][k] > i){
                        count++;
                        DFS(j, k, i);
                    }
                }
            }
            max = Math.max(max, count);
        }

        System.out.println(max);

    }

    static void DFS(int x, int y, int height){
        visited[x][y] = true;
        for (int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >=0 && ny >= 0 && nx < N && ny < N){
                if (!visited[nx][ny] && (land[nx][ny] > height)){
                    DFS(nx, ny, height);
                }
            }
        }
    }
}

해설

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

 

2468번: 안전 영역

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는

www.acmicpc.net

안전 영역과 비슷한 DFS계열 문제이다.

DFS의 핵심은 노드의 연결관계를 잘 파악해야 한다. 따라서 boolean 배열인 visited로 재방문을 막아야 한다.

 static StringTokenizer st;

    static int[][] land;
    static boolean[][] visited;

    static int N, count;

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

물이 잠기지 않는 지점은 대각선이 아닌, 가로와 세로로만 판단하므로 가로 세로만 있는 델타 배열을 이용한다.

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        land = new int[N][N];
        int maxHeight = 0;
        for (int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<N; j++){
                int h = Integer.parseInt(st.nextToken());
                land[i][j] = h;
                maxHeight = Math.max(maxHeight, h);
            }
        }
        int max = 0;
        //DFS
        for (int i=0; i<maxHeight; i++){
            count = 0;
            visited = new boolean[N][N];
            for (int j=0; j<N; j++){
                for (int k=0; k<N; k++){
                    if (!visited[j][k] && land[j][k] > i){
                        count++;
                        DFS(j, k, i);
                    }
                }
            }
            max = Math.max(max, count);
        }

        System.out.println(max);

    }

Main stack 안의 flow는 크게 다음의 2가지로 이루어진다.

 

1. 배열 채우기

2. DFS 사용하기

 

1. 배열 채우기

먼저 배열에 각 요소들을 담아준 뒤, 가장 높은 높이를 측정하기 위해서 maxHeight라는 변수를 설정하고 구한다.

 

2. DFS 사용하기

우리가 알고 싶은 것은 "연결되어있는 섬의 개수"이다.

전체 코드에서 DFS라는 단어가 들어가는 부분은 2부분이다.

[DFS를 사용하는 곳, DFS를 정의하는 곳]

이 두 군데 중 어느 곳에서 count를 늘리냐는 문제에서 구하라는 부분을 잘 읽고 나타내야 한다.

DFS를 사용하는 곳에서 count를 늘리면 "섬의 개수"를,

DFS를 정의하는 곳에서 count를 늘리면 "섬의 크기"를 구할 수 있게 된다.

우리는 섬의 개수를 구해야 하므로 DFS를 사용하는 곳에서 count를 늘려야 한다.

DFS를 시행하는 조건은 2개여야 한다.

1. 방문하지 않았을 것

2. 섬의 높이가 비가 오는 높이보다 초과해야 한다(>i)

 

static void DFS(int x, int y, int height){
        visited[x][y] = true;
        for (int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >=0 && ny >= 0 && nx < N && ny < N){
                if (!visited[nx][ny] && (land[nx][ny] > height)){
                    DFS(nx, ny, height);
                }
            }
        }
    }

 

마지막으로 DFS 함수를 정의한다.

델타 배열을 정의하고, 좌표가 0 이상 N 미만일 시 비가 오는 지점보다 높다면 DFS함수를 재실행하면 된다.

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

풀이

public class bojtest2 {
	static StringTokenizer st;

	static int[][] land;
	static boolean[][] visited;

	static int N,M, count;

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


	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		while (true){
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			if (N+M == 0) break;
			land = new int[M][N];
			visited = new boolean[M][N];
			for (int i = 0; i<M; i++){
				st = new StringTokenizer(br.readLine());
				for (int j=0; j<N; j++){
					land[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			// count 초기화
			count = 0;

			//DFS
			for (int i=0; i<M; i++){
				for (int j=0; j<N; j++){
					if(!visited[i][j] && land[i][j] == 1){
						count++;
						DFS(i, j);
					}
				}
			}
			sb.append(count).append("\n");
		}
		System.out.println(sb.toString());
	}

	static void DFS(int x, int y){
		visited[x][y] = true;
		for (int i=0; i<8; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < M && ny < N){
				System.out.println("nx , ny");
				if (!visited[nx][ny] && land[nx][ny] == 1){
					DFS(nx, ny);
				}
			}
		}
	}
}

해설

DFS 정복 주간 처음으로 풀어본 문제이다.

이런 길찾기류 문제가 DFS의 대표적인 유형이다.

DFS의 핵심은 노드의 연결관계를 잘 파악해야 한다. 따라서 boolean 배열인 visited로 재방문을 막아야 한다.

static StringTokenizer st;

static int[][] land;
static boolean[][] visited;

static int N,M, count;

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

문제를 보면 앞뒤, 위아래, 그리고 대각선까지 연결하는 것이 같은 땅이라고 해석하고 있다.

그래서 dx, dy를 델타 배열로 주었다.

public static void main(String[] args) throws IOException {
 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 StringBuilder sb = new StringBuilder();
 while (true){
  st = new StringTokenizer(br.readLine());
  N = Integer.parseInt(st.nextToken());
  M = Integer.parseInt(st.nextToken());
  if (N+M == 0) break;
  land = new int[M][N];
  visited = new boolean[M][N];
  for (int i = 0; i<M; i++){
   st = new StringTokenizer(br.readLine());
   for (int j=0; j<N; j++){
    land[i][j] = Integer.parseInt(st.nextToken());
   }
  }
// count 초기화
 count = 0;

//DFS
 for (int i=0; i<M; i++){
  for (int j=0; j<N; j++){
   if(!visited[i][j] && land[i][j] == 1){
     count++;
     DFS(i, j);
    }
   }
  } 
  sb.append(count).append("\n");
 }
 System.out.println(sb.toString());
}

Main stack 안의 flow는 크게 다음의 2가지로 이루어진다.

 

1. 배열 채우기

2. DFS 사용하기

 

1. 배열 채우기

먼저, 0 0이 주어져야 끝나므로 breakpoint를 걸어둔다.

숫자를 입력받고, land와 visited 배열을 초기화 시켜주고,

섬의 개수를 나타낼 count를 초기화시켜준다.

 

2. DFS 사용하기

우리가 알고 싶은 것은 "연결되어있는 섬의 개수"이다.

전체 코드에서 DFS라는 단어가 들어가는 부분은 2부분이다.

[DFS를 사용하는 곳, DFS를 정의하는 곳]

이 두 군데 중 어느 곳에서 count를 늘리냐는 문제에서 구하라는 부분을 잘 읽고 나타내야 한다.

DFS를 사용하는 곳에서 count를 늘리면 "섬의 개수"를,

DFS를 정의하는 곳에서 count를 늘리면 "섬의 크기"를 구할 수 있게 된다.

우리는 섬의 개수를 구해야 하므로 DFS를 사용하는 곳에서 count를 늘려야 한다.

DFS를 시행하는 조건은 2개여야 한다.

1. 방문하지 않았을 것

2. 섬이라는 표시(1)가 되어있을 것

static void DFS(int x, int y){
 visited[x][y] = true;
 for (int i=0; i<8; i++){
  int nx = x + dx[i];
  int ny = y + dy[i];
   if (nx >= 0 && ny >= 0 && nx < M && ny < N){
    if (!visited[nx][ny] && land[nx][ny] == 1){
     DFS(nx, ny);
    }
   }
  }
 }

마지막으로 DFS 함수를 정의한다.

우리가 방문하게 되면 방문했다고 표기를 해야 하므로 visited배열을 true값으로 바꿔준다.(초기화시 false)

또 델타 배열을 돌면서 판단하는데, 배열을 돌 때는 늘 Array의 크기 안에 좌표가 있어야 한다.(nx의 조건)

방문하지 않았고(!visited[x][y]) 섬이라는 표시(land[nx][ny] == 1)가 되어있으면 (nx, ny)의 좌표로 넘어가서

DFS를 새로 시행한다는 함수다.

 

이러한 유형의 문제는 

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

 

2468번: 안전 영역

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는

www.acmicpc.net

에서 한 번 더 연습할 수 있다.

+ Recent posts