https://www.acmicpc.net/problem/2178
- 풀이
최단 경로를 찾는 문제이므로 BFS를 사용하면 된다.
1. 입력
각각의 수가 붙어서 입력으로 주어지므로 분리 시켜줘야 한다.
for (int i=0; i<N; i++) {
int line = Integer.parseInt(bf.readLine());
for (int j=0; j<M; j++) {
arr[i][j] = line/(int)(Math.pow(10, M-j-1));
line%=(int)(Math.pow(10, M-j-1));
}
처음에는 이렇게 10의 제곱을 이용한 몫으로 구분을 해주었지만, M의 범위가 100까지이기 때문에 line이 너무 큰 수가 되어 정수형 타입에 담지 못 하는 오류가 났다.
// 입력
for (int i=0; i<N; i++) {
String s = bf.readLine();
for (int j=0; j<M; j++) {
arr[i][j] = (int)s.charAt(j)-48;
}
}
따라서 이렇게 String으로 받아 charAt으로 분할해준 뒤 int로 형변환해서 읽었다.
문자열 ‘0’은 int로 변환했을 때 48이 되고 문자열 ‘1’은 int로 변환했을 때 49가 되므로 -48 시켜주었다.
2. BFS
좌표를 큐에 담는 방법이 고민이었는데, 좌표 클래스를 만들어서 큐에 넣어주면 된다고 한다.
따라서 이렇게 Pair라는 클래스를 만들어주었다.
static class Pair{
int x, y, level;
Pair(int x, int y, int level){
this.x = x;
this.y = y;
this.level = level;
}
}
x, y는 좌표를 뜻하고, level은 시작점부터 이 점까지의 최단 거리를 담은 변수이다.
while문은 시작점부터 시작해서 (N,M)을 찾을 때까지 반복되는데, 기본적인 BFS 형태와 동일하지만 인접한 노드를 큐에 넣을 때 level을 1씩 증가시켜서 거리를 기록하였다는 차이가 있다.
static void BFS(int startX, int startY) {
Queue <Pair> que = new ArrayDeque<>();
// 시작점 Enqueue
Pair start = new Pair(startX, startY, 1);
que.add(start);
isVisited[startX][startY] = true;
while(!que.isEmpty()) {
Pair now = que.poll();
for (int i=0; i<4; i++) { // 기준점 상하좌우 탐색
Pair next = new Pair(now.x + dx[i], now.y + dy[i], now.level+1);
// 범위 벗어나면 X
if (next.x >= N || next.x < 0 || next.y < 0 || next.y>=M) continue;
// 길이 아니면 X
if (arr[next.x][next.y]==0) continue;
// 이미 방문했으면 X
if (isVisited[next.x][next.y]) continue;
// 종점이면 종료
if (next.x == N-1 && next.y == M-1) {
System.out.println(next.level);
return;
}
// Enqueue
que.add(next);
isVisited[next.x][next.y] = true;
}
}
}
전체코드
더보기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static int arr[][];
static int cnt;
static int [] dx = {-1,1,0,0}; // 상하좌우
static int [] dy = {0,0,-1,1};
static boolean [][] isVisited;
static class Pair{
int x, y, level;
Pair(int x, int y, int level){
this.x = x;
this.y = y;
this.level = level;
}
}
static void BFS(int startX, int startY) {
Queue <Pair> que = new ArrayDeque<>();
// 시작점 Enqueue
Pair start = new Pair(startX, startY, 1);
que.add(start);
isVisited[startX][startY] = true;
while(!que.isEmpty()) {
Pair now = que.poll();
for (int i=0; i<4; i++) { // 기준점 상하좌우 탐색
Pair next = new Pair(now.x + dx[i], now.y + dy[i], now.level+1);
// 범위 벗어나면 X
if (next.x >= N || next.x < 0 || next.y < 0 || next.y>=M) continue;
// 길이 아니면 X
if (arr[next.x][next.y]==0) continue;
// 이미 방문했으면 X
if (isVisited[next.x][next.y]) continue;
// 종점이면 종료
if (next.x == N-1 && next.y == M-1) {
System.out.println(next.level);
return;
}
// Enqueue
que.add(next);
isVisited[next.x][next.y] = true;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int [N][M];
isVisited = new boolean [N][M];
// 입력
for (int i=0; i<N; i++) {
String s = bf.readLine();
for (int j=0; j<M; j++) {
arr[i][j] = (int)s.charAt(j)-48;
}
}
// 경로 찾기
BFS(0,0);
}
}
'개발 > 코딩테스트' 카테고리의 다른 글
정올 1828번: 냉장고 [JAVA] (0) | 2023.03.18 |
---|---|
백준 1260번: DFS와 BFS [JAVA] (0) | 2023.03.18 |
백준 1991번: 트리순회 [JAVA] (0) | 2023.03.18 |
2019 카카오 개발자 겨울 인턴십 - 크레인 인형뽑기 게임 [JAVA] (0) | 2023.03.16 |
백준 1931번: 회의실 배정 [JAVA] (0) | 2023.03.16 |
댓글