BOJ G4 1261 알고스팟 JAVA
1261번: 알고스팟
첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미
www.acmicpc.net
문제 읽기
이 문제는.. 처음에 읽었을 때 다익스트라를 공부한 후에 풀려고 했던 BOJ 9376 탈옥 문제의 쉬운 버전처럼 느껴졌다.
사실 MAP 형태로 주어지는 문제에서 다익스트라로 풀어본 적이 없어서, ‘이걸 어떻게 다익스트라로 봐야 하지?’란 생각으로 도저히 방법을.. 모르겠더라.
삽질. 내가 그래프를 만들자(?)
그래서 처음에는 좀 멍청한(?) 짓을 했다. 0으로 묶인 부분끼리 한 집합으로 보고, 이걸 노드로 보고 그 사이의 1 최소 개수를 카운팅해서 내가 그래프를 만들었다.. (ㅋㅋ).. 근데 하다 보니 이게 맞나? 싶었고, 그래도 끈기를 가지고 끝까지 해서 예제 답은 맞았는데, 제출하니 틀렸더라.(ㅠㅠ)
그래서 그냥 단순하게 생각하자 해서 BFS로 했는데 맞긴 했다. 근데 너무 찜찜한 이 느낌..!! 여러 풀이를 정리해보자.
문제 풀기
풀이 1) BFS + PQ
내가 푼 방식이다. 그냥 depth를 활용한 BFS를 하면서 일반 Queue 대신 PQ를 사용하여 cost를 최소인 걸 먼저 꺼내는 식으로 했다. 그리고 마지막 지점에 도달하면 바로 리턴!
package ps.ㄱSolving;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BOJ_G4_1261_알고스팟 {
static class Pos{
int r, c;
int depth;
public Pos(int r, int c, int depth){
this.r = r;
this.c = c;
this.depth = depth;
}
}
static int N, M;
static int[][] map;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
map = new int[N][M];
for (int i = 0; i < N; i++){
String[] split = in.readLine().split("");
for (int j = 0; j < M; j++){
map[i][j] = Integer.parseInt(split[j]);
}
}
bfs(0, 0);
}
static int[] dr = {-1, 1, 0, 0};
static int[] dc = {0, 0, -1, 1};
private static void bfs(int i, int j) {
PriorityQueue<Pos> q = new PriorityQueue<>(new Comparator<Pos>() {
@Override
public int compare(Pos o1, Pos o2) {
return o1.depth - o2.depth;
}
});
boolean[][] visited = new boolean[N][M];
q.offer(new Pos(i, j, 0));
visited[i][j] = true;
while(!q.isEmpty()){
Pos cur = q.poll();
if ((cur.r == N-1) && (cur.c == M-1)){
System.out.println(cur.depth);
return;
}
for (int di = 0; di < 4; di++){
int nr = cur.r + dr[di];
int nc = cur.c + dc[di];
if (nr < 0 || nr >= N || nc < 0 || nc >= M || visited[nr][nc]) continue;
visited[nr][nc] = true;
if (map[nr][nc] == 1) q.offer(new Pos(nr, nc, cur.depth + 1));
else q.offer(new Pos(nr, nc, cur.depth));
}
}
}
}
풀이 2) 0-1 BFS
이건 이번에 처음 안 알고리즘이다.
간단하게 설명하자면, 모든 간선의 비용이 0 또는 1일 때 적용할 수 있는 알고리즘으로, 최단 경로를 찾는 알고리즘이다. 시간복잡도가 O(V + E)로, 이런 특수한 경우에는 다익스트라보다 더 효율적인 알고리즘이라 한다!
0-1 BFS 알고리즘 설명은 다음 글을 참고 하면 좋을 것이다.
0-1 BFS
0-1 BFS란? 💡 0-1 BFS 가중치가 0 또는 1로만 주어진 그래프에서, 시작 노드가 주어졌을 때 다른 모든 노드로의 최단 경로를 찾고자 할 때 사용하는, BFS를 응용한 알고리즘이다. 보편적으로 그래프
rue-mi.tistory.com
package ps.ㄱSolving;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BOJ_G4_1261_알고스팟 {
static class Pos{
int r, c;
int depth;
public Pos(int r, int c){
this.r = r;
this.c = c;
}
}
static int N, M;
static int[][] map;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
map = new int[N][M];
for (int i = 0; i < N; i++){
String[] split = in.readLine().split("");
for (int j = 0; j < M; j++){
map[i][j] = Integer.parseInt(split[j]);
}
}
zeroOnebfs(new Pos(0, 0));
System.out.println(dist[N-1][M-1]);
}
static int[] dr = {-1, 1, 0, 0};
static int[] dc = {0, 0, -1, 1};
static int[][] dist;
private static void zeroOnebfs(Pos start) {
//dec, dist
Deque<Pos> dec = new ArrayDeque();
dist = new int[N][M];
for (int i = 0; i < N; i++){
Arrays.fill(dist[i], Integer.MAX_VALUE);
}
dist[start.r][start.c] = 0;
dec.add(start);
while(!dec.isEmpty()){
Pos cur = dec.pollFirst();
for (int di = 0; di < 4; di++){
int nr = cur.r + dr[di];
int nc = cur.c + dc[di];
if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
//거리가 갱신되면
if (dist[nr][nc] > dist[cur.r][cur.c] + map[nr][nc]){
dist[nr][nc] = dist[cur.r][cur.c] + map[nr][nc];
if (map[nr][nc] == 0) dec.addFirst(new Pos(nr, nc));
else dec.addLast(new Pos(nr, nc));
}
}
}
}
}
풀이 3) Dijkstra
0-1 BFS를 보다 보니 아 그냥 각각의 모든 칸을 정점으로 보면 되겠구나 싶었다. 굳이 묶을 필요 없이..(ㅠㅠ) 그래도 얻을 게 많은 삽질이었다..
다익스트라 알고리즘 설명은 다음 글을 참고하면 좋을 것이다.
다익스트라, Dijkstra Algorithm
코딩 문제에서 많이 볼 수 있는 그래프와 관련된 알고리즘을 공부해보자. 그래프에서 최단 거리를 구하는 알고리즘은 다음과 같은 것들이 있다. 💡 그래프의 최단 거리 구하는 알고리즘 1. 다익
rue-mi.tistory.com
package ps.ㄱSolving;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BOJ_G4_1261_알고스팟 {
static class Pos{
int r, c;
int depth;
public Pos(int r, int c, int depth){
this.r = r;
this.c = c;
this.depth = depth;
}
}
static int N, M;
static int[][] map;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
map = new int[N][M];
for (int i = 0; i < N; i++){
String[] split = in.readLine().split("");
for (int j = 0; j < M; j++){
map[i][j] = Integer.parseInt(split[j]);
}
}
zeroOnebfs(new Pos(0, 0, 0));
System.out.println(dist[N-1][M-1]);
}
static int[] dr = {-1, 1, 0, 0};
static int[] dc = {0, 0, -1, 1};
static int[][] dist;
private static void zeroOnebfs(Pos start) {
//dec, dist
PriorityQueue<Pos> pq = new PriorityQueue<>(new Comparator<Pos>() {
@Override
public int compare(Pos o1, Pos o2) {
return o1.depth - o2.depth;
}
});
dist = new int[N][M];
for (int i = 0; i < N; i++){
Arrays.fill(dist[i], Integer.MAX_VALUE);
}
dist[start.r][start.c] = 0;
pq.offer(start);
while(!pq.isEmpty()){
Pos cur = pq.poll();
for (int di = 0; di < 4; di++){
int nr = cur.r + dr[di];
int nc = cur.c + dc[di];
if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
//거리가 갱신되면
if (dist[nr][nc] > dist[cur.r][cur.c] + map[nr][nc]){
dist[nr][nc] = dist[cur.r][cur.c] + map[nr][nc];
pq.offer(new Pos(nr, nc, cur.depth + map[nr][nc]));
}
}
}
}
}