코딩테스트 연습 스터디 진행중 입니다. ✍✍✍
Notion : https://www.notion.so/1c911ca6572e4513bd8ed091aa508d67

문제

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

[나의 풀이]

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

public class Correct {

    static int[][] map;
    static int n;
    static int m;
    static boolean[][] visited;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };

    static void bfs(int x, int y) {

        // bfs는 Queue 활용
        Queue<int[]> queue1 = new LinkedList<>();
        queue1.add(new int[] { x, y });

        while (!queue1.isEmpty()) {
            int now[] = queue1.poll();
            int nowX = now[0];
            int nowY = now[1];

            for (int i = 0; i < 4; i++) {
                int nextX = nowX + dx[i];
                int nextY = nowY + dy[i];

                if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m) {
                    continue;
                }
                if (visited[nextX][nextY] || map[nextX][nextY] == 0) {
                    continue;
                }

                queue1.add(new int[] { nextX, nextY });

                // 같은 층이면 같은 값을 가짐!
                map[nextX][nextY] = map[nowX][nowY] + 1;
                visited[nextX][nextY] = true;
            }
        }
    }

    public static void main(String[] args) throws IOException {

        // 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        map = new int[n][m];

        for (int i = 0; i < n; i++) {
            String input = br.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(Character.toString(input.charAt(j)));
            }
        }

        // 방문한 위치 true or false
        visited = new boolean[n][m];

        visited[0][0] = true;

        // bfs
        bfs(0, 0);

        // 도착위치의 값만 출력하면 됌!
        System.out.println(map[n - 1][m - 1]);
    }
}

dfs or bfs를 활용해야하는 문제입니다.

root좌표 (0,0)에서 상하좌우로 탐색하여 도착하는 최소한의 이동횟수를 출력하는 문제입니다. 푸는 과정에서 상하좌우로 탐색하고 도착하는 방법까지는 구현하였으나 최소 이동 횟수를 구하는 방법이 떠오르지 않아 구글링으로 해결했습니다...😱😱😱

bfs를 활용하여 그래프 상 같은 층에 있는 좌표들의 수는 일치시키고 깊게 내려갈수록 좌표의 값들을 +1씩하여 최종 도착 좌표의 값만 출력하면 되는 간단한(?) 방법이 있었습니다. 오늘도 하나 깨달음을 얻었습니다!🐰🐰🐰

아래는 제가 구현한 (최소X) 도착좌표까지만 도달할 수 있는 코드입니다.

// 오답!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static void dfs(int[][] board, int x, int y, boolean[][] visitied,int cnt) {

        visitied[x][y] = true;

        if (x == board.length - 1 && y == board[0].length - 1) {
            System.out.println(cnt+1);
            return;
        }

        int[] moves_x = new int[] { 1, 0, 0, -1 };
        int[] moves_y = new int[] { 0, 1, -1, 0 };

        for (int i = 0; i < moves_x.length; i++) {
            if (x + moves_x[i] >= 0 && x + moves_x[i] < board.length && y + moves_y[i] >= 0
                    && y + moves_y[i] < board[0].length) {
                if (visitied[x + moves_x[i]][y + moves_y[i]] == false) {
                    if (board[x + moves_x[i]][y + moves_y[i]] == 1) {
                        cnt++;
                        dfs(board, x + moves_x[i], y + moves_y[i], visitied,cnt);
                    }
                }

            }
        }

    }

    public static void main(String[] args) throws IOException {

        // board 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int row_num = Integer.parseInt(st.nextToken());
        int column_num = Integer.parseInt(st.nextToken());

        int[][] board = new int[row_num][column_num];

        for (int i = 0; i < row_num; i++) {
            int[] column = new int[column_num];
            String map = br.readLine();
            for (int j = 0; j < column_num; j++) {
                column[j] = Integer.parseInt(Character.toString(map.charAt(j)));
            }
            board[i] = column;
        }

        // root 위치
        int x = 0;
        int y = 0;

        // 방문한 위치 true or false
        boolean[][] visitied = new boolean[board.length][board[0].length];

        // 움직인 칸
        int cnt = 0;

        // 미로 탐색
        dfs(board, x, y, visitied,cnt);
    }

}

감사합니다!😊😊😊