백준 2178 - 미로탐색, 너비우선, 깊이우선, 프로그래머스, 알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, 풀이과정, Leetcode, 릿코드, 코딩테스트, Tech interview, search, greedy, baekjoon, acmicpc..

 

입력이 Scanner로 넣으면 계속 런타임에러가 나서 바꾸고 됨

 

// Process

// 1. Input n, m, maze array

// 2. Prepare queue for BFS

// 3. 시작부터 목적지(가장오른쪽가장아래) 도착, 또는 큐가 빌 때까지 반복한다.

//  3.1. 큐에서 빼서, 이동이 유효하면 4방향 중 이동 가능한 곳을 찾아서 큐에 넣어둔다.

//  3.2. 목적지에 도착했는지 확인한다. 도착했으면, 해당 depth를 세고 종료한다.

// 4. 센 카운트 출력한다.

 

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

class Node {
    int row = 0;
    int col = 0;
    int depth = 0;
    
    public Node(int row, int col, int depth) {
        this.row = row;
        this.col = col;
        this.depth = depth;
    }

}

class SearchMaze {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // Scanner scanner = new Scanner(System.in);
        // int n = scanner.nextInt();
        // int m = scanner.nextInt();
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        int[][] maze = new int[n][m];
        boolean[][] movable = new boolean[n][m];

        for (int i = 0; i < n; ++i) {
            String line = br.readLine();
            for (int j = 0; j < line.length(); ++j) {
                if (line.charAt(j) == '1') {
                    maze[i][j] = 1;
                    movable[i][j] = true;
                } else if (line.charAt(j) == '0') {
                    maze[i][j] = 0;
                }
            }
        }
        
        int count = 0;

        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(0,0,1));
        
        boolean isFound = false;
        while (queue.size() > 0 && !isFound) {
            Node pair = queue.poll();

            if (movable[pair.row][pair.col]) {
                movable[pair.row][pair.col] = false;

                if (pair.row - 1 >= 0 && movable[pair.row-1][pair.col])
                    queue.add(new Node(pair.row - 1, pair.col, pair.depth+1));
                if (pair.row + 1 < n && movable[pair.row+1][pair.col])
                    queue.add(new Node(pair.row + 1, pair.col, pair.depth+1));
                if (pair.col - 1 >= 0 && movable[pair.row][pair.col-1])
                    queue.add(new Node(pair.row, pair.col - 1, pair.depth+1));
                if (pair.col + 1 < m && movable[pair.row][pair.col+1])
                    queue.add(new Node(pair.row, pair.col + 1, pair.depth+1));
                
                if (pair.row == n-1 && pair.col == m-1) {
                    count = pair.depth;
                }
            }
        }

        System.out.println(count);

        // scanner.close();
    }
}

 

2021.04.06 - [Algorithm/Baekjoon_acmicpc] - 백준 2437 - 저울, 문제풀이, 프로그래머스, 알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, 풀이과정, Leetcode, 릿코드, 코딩테스트, Tech interview, search, greedy, baekjoon, acmicpc

백준 2437 - 저울, 문제풀이, 프로그래머스, 알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorith

2021.03.01 - [Algorithm/Programmers] - 힙 03 - 이중우선순위큐, 프로그래머스, 알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, 풀이과정, Leetcode, 릿코드, 코딩테스트, Tech interview, Heap, 힙

힙 03 - 이중우선순위큐, 프로그래머스, 알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm,

 

2018.12.26 - [Programming/Software Architecture] - Perfecting OO's Small Classes and Short Methods. 완벽한 객체지향의 작은 클래스와 짧은 메소드, Book:ThoughtWorks Anthology, Java,cpp,자바,oop,좋은코드,객체지향프로그래밍 (1)

Perfecting OO's Small Classes and Short Methods. 완벽한 객체지향의 작은 클래스와 짧은 메소드, Book:ThoughtWor