[Baekjoon] 1261_알고스팟

Gold IV

문제(출처: https://www.acmicpc.net/problem/1261)

---

< 알고스팟>

 

문제 풀이

 

bfs를 활용하여 벽을 몇 개 부수어야 하는지를 세어준다.

 

 

 - my solution (Java)

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 _1261_ { // 알고스팟
	static int arr[][], m, n, result;
	static int visited[][];

	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());

		arr = new int[n][m];
		visited = new int[n][m];
		result=0;

		for (int i = 0; i < n; i++) {
			String s = bf.readLine();
			for (int j = 0; j < m; j++) {
				arr[i][j] = s.charAt(j)-'0';
				visited[i][j] = -1;
			}
		}
		bfs();
		System.out.println(result);
	}

	private static void bfs() {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { 0, 0 });
		visited[0][0] = 0;
		boolean flag = false;

		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int i = 0; i < 4; i++) {
				int x = temp[0] + dx[i];
				int y = temp[1] + dy[i];
				if (x >= 0 && x < n && y >= 0 && y < m) {
					if (arr[x][y] == 0 && (visited[x][y]==-1 ||visited[x][y]>visited[temp[0]][temp[1]])) {
						flag = true;
						visited[x][y] = visited[temp[0]][temp[1]];
					} else {
						if (visited[x][y] == -1 || visited[temp[0]][temp[1]] + 1 < visited[x][y]) {
							visited[x][y] = visited[temp[0]][temp[1]] + 1;
							flag = true;
						}
					}
					if (flag) {
						queue.add(new int[] { x, y });
						flag=false;
					}
				}
			}
		}
		result=visited[n-1][m-1];

	}
}

 

• Main
  • m, n 입력
  • arr : 미로
  • visited : 부숴야 하는 벽의 수
  • result : 부숴야 하는 벽의 최소 개수
  • bfs 함수 호출 후 result 출력
• bfs
  
  • queue에 시작 위치인 (0,0) 넣고 visited를 0으로 저장
  • queue가 빌 때까지 반복 -> 상하좌우 탐색 -> 빈 방 or 벽일 때 구분하여 부숴야 하는 벽의 수가 최소가 되도록 값을 update 및 queue에 추가
  • queue가 비었을 때 result 값을 update

---

생각🤔

 

---