접근법 : BFS
한 좌표로부터 인접한 좌표를 하나씩 방문해가면서 각 좌표의 최단거리를 구해낸다.
풀이 과정
java 구현 코드
package ch08_BFS;
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 p2178 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.valueOf(st.nextToken()); // 세로 길이 n
int m = Integer.valueOf(st.nextToken()); // 가로 길이 m
char[][] mazeArr = new char[n + 2][m + 2]; // 미로를 저장할 배열
// 미로 배열 세팅하기
for (int i = 0; i < n; i++) {
String input = br.readLine();
for (int j = 0; j < m; j++) {
mazeArr[i + 1][j + 1] = input.charAt(j);
}
}
int[] dx = {1, 0, -1, 0}; // 우상좌하
int[] dy = {0, 1, 0, -1};
// BFS
Queue<Point> queue = new LinkedList<>(); // 큐 생성
int[][] distance = new int[n + 2][m + 2]; // 각 좌표에서 (1,1)까지 최단거리 저장 배열
distance[1][1] = 0; // (0,0)의 최단거리 값 0으로 세팅 (생략 가능)
queue.add(new Point(1, 1)); // (1,1) 좌표 enqueue
while(!queue.isEmpty()) { // queue가 빌 때까지 반복
Point tmp = queue.remove(); // dequeue
int tmpX = tmp.X;
int tmpY = tmp.Y;
int tmpDistance = distance[tmpX][tmpY];
for (int i = 0; i < 4; i++) { // 꺼낸 좌표의 우상좌하 순으로 탐색
int dX = tmpX + dx[i];
int dY = tmpY + dy[i];
if (mazeArr[dX][dY] == '1' && distance[dX][dY] == 0) { // 갈 수 있는 경로인데 아직 방문 안 했으면
distance[dX][dY] = tmpDistance + 1; // dequeue한 좌표의 최단거리에 1 더하기
queue.add(new Point(dX, dY)); // enqueue
}
}
}
System.out.println(distance[n][m] + 1);
}
}
class Point {
int X;
int Y;
Point(int X, int Y) {
this.X = X;
this.Y = Y;
}
}
풀이 날짜 : 2023/12/22 (금)
내년에 코딩테스트 응시하려면 12월에 남은 며칠동안 알고리즘 공부 진도를 빨리 나가야 하는데....자꾸 공부에 집중이 잘 안 된다. 아무래도 도파민 중독으로 한 곳에 집중을 제대로 못하는 것 같다.
오늘 오전은 집에서 뒹굴거리느라 시간을 낭비했지만 오후에 뒤늦게라도 정석에 온 내 자신에게 칭찬해주자 👏
일단 오늘 하루에 후회 없도록, 핸드폰 끄고 11시까지 열심히 달려야겠다.