[BOJ] 알고스팟

[1261] 알고스팟

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

• 미로는 N*M 크기이고, 총 1*1 크기의 방으로 이루어져 있다.
• 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.
• (x,y)에 있을 때, 이동할 수 있는 방은 상, 하, 좌, 우이다.
• (1,1)에서 (N,M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 문제

 

 

Solution

• 덱을 사용한 BFS 풀이 방법
• BFS 탐색을 벽을 부순 횟수에 따라서 나누어서 수행해야 한다.
• 어차피 벽을 뚫는다와 안 뚫는다로 나누어지기 떄문에, 덱을 사용한다.
• 벽을 뚫는 경우에는 뒤에, 안 뚫는 경우에는 앞에 추가한다.
• map[][]에 몇 번 뚫고 지나간 경로인지 횟수를 넣어준다.

 

 

소스코드

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	int[] count;
	int[][] map;
	int[][] visited;
	int[] dx = { 1, -1, 0, 0 };
	int[] dy = { 0, 0, 1, -1 };
	int n, m;

	class Dot {
		private int x, y;

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

	public void go() {
		Scanner sc = new Scanner(System.in);
		m = sc.nextInt();
		n = sc.nextInt();
		sc.nextLine();
		map = new int[n][m];
		visited = new int[n][m];
		String s;
		for (int i = 0; i < n; i++) {
			s = sc.nextLine();
			for (int j = 0; j < m; j++) {
				map[i][j] = s.charAt(j) - '0';
			}
		}
		bfs(new Dot(0, 0));
		System.out.println(map[n - 1][m - 1]);
	}

	public void bfs(Dot dot) {
		Deque<Dot> q = new LinkedList<>();
		q.addFirst(dot);
		visited[dot.x][dot.y] = 1;
		while (!q.isEmpty()) {
			Dot cur = q.poll();
			int nx, ny;
			for (int i = 0; i < 4; i++) {
				nx = cur.x + dx[i];
				ny = cur.y + dy[i];

				if (nx < 0 || ny < 0 || nx >= n || ny >= m)
					continue;
				if (visited[nx][ny] == 1)
					continue;

				if (map[nx][ny] == 0) { // 빈 방인 경우
					map[nx][ny] = map[cur.x][cur.y];
					q.addFirst(new Dot(nx, ny));
					visited[nx][ny] = 1;
				} else {	// 벽인 경우
					map[nx][ny] = map[cur.x][cur.y] + 1;
					q.addLast(new Dot(nx, ny));
					visited[nx][ny] = 1;
				}
			}
		}
	}

	public static void main(String[] args) {
		Main main = new Main();
		main.go();
	}
}dsfs