[Java] 백준 - 1261번: 알고스팟

6월 28일(금) - 그래프와 순회(1261번)

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

---

최초 생각 정리

---

문제점

---

풀이

(풀이출처 -> https://loosie.tistory.com/200)

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

import java.util.*;

class Node implements Comparable<Node>{
    int x;
    int y;
    int wall;

    public Node(int x, int y, int wall){
        this.x = x;
        this.y = y;
        this.wall = wall;
    }

    @Override
    public int compareTo(Node o){
        return this.wall - o.wall;
    }
}

public class Main {

    static int M, N;
    static int[][] map;
    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());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[M][N];

        for(int i=0; i<M; i++)
        {
            String[] line = br.readLine().split("");
            for(int j=0; j<N; j++)
            {
                int num = Integer.parseInt(line[j]);
                map[i][j] = num;
            }
        }

        System.out.println(bfs(0, 0));
    }

    static int bfs(int x, int y){
        Queue<Node> q = new PriorityQueue<>();
        boolean[][] visited = new boolean[M][N];

        visited[y][x] = true;
        q.add(new Node(x,y,0));

        while (!q.isEmpty())
        {
            Node pos = q.poll();

            int post_x = pos.x;
            int post_y = pos.y;
            int post_wall = pos.wall;

            if(post_x == N-1 && post_y == M-1)
            {
                return post_wall;
            }

            for(int i=0; i<4; i++)
            {
                int next_x = post_x + dx[i];
                int next_y = post_y + dy[i];

                if(next_x < 0 || next_y < 0 || next_x > N-1 || next_y > M-1)
                {
                    continue;
                }

                if(visited[next_y][next_x])
                {
                    continue;
                }

                visited[next_y][next_x] = true;
                if(map[next_y][next_x] == 0)
                {
                    q.add(new Node(next_x, next_y, post_wall));
                }
                else
                {
                    q.add(new Node(next_x, next_y, post_wall + 1));
                }
            }
        }

        return 0;
    }
}

---