문제 링크
1981번: 배열에서 이동
n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를
www.acmicpc.net
주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}문제 설명
접근 방법
이 문제에 핵심
1. N × N 배열에서 (1, 1)에서 (N, N)까지 이동하려고 한다.
2. 이동하는 방법은 상, 하, 좌, 우 방향으로 1칸씩 이동이 가능하다.
3. (N, N)까지 도착하는 경로에서 최대값과 최소값의 차이 중 가장 작은 값을 결과로 출력합니다.
알고리즘 진행 순서.
1. 입력된 정보를 저장합니다.
2. 이분 탐색을 통해 나올 수 있는 차이값을 탐색하고, BFS을 통해서 (N, N)까지 갈 수 있는지 확인합니다.
3. 이분탐색을 통해 얻은 최소값을 결과로 출력합니다.
이분 탐색(차이값 탐색)
나올 수 있는 차이값을 기준으로 이분탐색을 진행합니다.
나올 수 있는 차이값을 구하기 위해서, 배열에 입력값을 받을 때 최소값과 최대값을 구해야합니다.
만약,
최대값 : 20
최소값 : 5
이분 탐색을 시작하는 범위는
Start : 0
End : 20(max) - 5(min) = 15
End의 값이 Max - Min이 되는 이유
▶ 주어진 배열의 최대값과 최소값이기 때문에 해당 값보다 큰 차이값이 발생할 수 없습니다.
위 범위를 기준으로 이분탐색을 통해서 차이가 발생하는 값들을 탐색합니다.
이분 탐색을 진행할 때에는 2가지의 경우가 발생합니다.
1. 해당 차이값을 기준으로 BFS을 했을 때 (0, 0) → (N, N)에 도달하지 못할 때
start = mid + 1
▶ 주어진 값보다 작아도 도달하지 못하기 때문에 더 큰 범위를 탐색해야 합니다.
2. 해당 차이값을 기준으로 BFS을 했을 때 (0, 0) → (N, N)에 도달했을 때
end = mid - 1
result = Math.min(result, mid)
▶ 주어진 값이 도달하기 때문에 해당 값보다 큰 범위는 탐색할 필요가 없으며, 도달하기 때문에 최소값인지 비교합니다.
BFS을 통해서 (1, 1) → (N, N) 도달할 수 있는지 확인
배열에 존재하는 값이 1 ~ 9까지 존재한다고 가정했을 때, 차이가 5인 경우는
(1, 6), (2, 7), (3, 8), (4, 9) : 4가지 경우
4가지 경우 중 1개라도 (1, 1) → (N, N) 도달한다면 차이가 5일 때에는 도달할 수 있습니다.
결국, BFS을 1번을 진행하는 것이 아닌 차이가 발생할 수 있는 범위의 경우를 구한 뒤 반복적으로 BFS을 통해서 도달하는지 확인해야 합니다.
BFS을 이동할 때에도 (s, e) 범위에 값에 해당하는 값들로만 탐색을 진행해야 합니다.
※ 해당 범위에 있어야 현재 차이가 성립하기 때문입니다.
또한 시작 위치(1, 1)의 값도 s ≤ (1, 1) ≤ e 를 만족해야 합니다.
※예제입력 과정을 확인하시면 이해하시기 편하실 것입니다.
예제입력 1.
1. 입력된 정보를 저장합니다.
N : 5
| 1 | 1 | 3 | 6 | 8 |
| 1 | 2 | 2 | 5 | 5 |
| 4 | 4 | 0 | 3 | 3 |
| 8 | 0 | 2 | 3 | 4 |
| 4 | 3 | 0 | 2 | 1 |
2. 이분 탐색을 통해 나올 수 있는 차이값을 탐색하고, BFS을 통해서 (N, N)까지 갈 수 있는지 확인합니다.
배열의 최대값, 최소값 구하기
배열의 Max : 8
배열의 Min : 0
이분 탐색 진행.
Start : 0
End : 8
mid = (0 + 8) ÷ 2 : 4
차이가 4일 때
나올 수 있는 경우의 수
{ (0, 4), (1, 5), (2, 6), (3, 7), (4, 8) }
(0, 4)일 때 BFS 탐색 진행
| 1 | 1 | 3 | 6 | 8 |
| 1 | 2 | 2 | 5 | 5 |
| 4 | 4 | 0 | 3 | 3 |
| 8 | 0 | 2 | 3 | 4 |
| 4 | 3 | 0 | 2 | 1 |
도달 성공!!
차이 4는 (1, 1) → (N, N)까지 도달할 수 있습니다.
end = mid - 1 : 3
result = Math.min(result, mid) : 4
다음 이분 탐색 진행
Start : 0
End : 3
mid = (0 + 3) ÷ 2 : 1
차이가 1일 때
나올 수 있는 경우의 수
{ (0, 1), (1, 2), (2, 3), ..., (7, 8) }
(0, 1)일 때 BFS 탐색 진행
| 1 | 1 | 3 | 6 | 8 |
| 1 | 2 | 2 | 5 | 5 |
| 4 | 4 | 0 | 3 | 3 |
| 8 | 0 | 2 | 3 | 4 |
| 4 | 3 | 0 | 2 | 1 |
도달 실패!!
(1, 2)일 때 BFS 탐색 진행
| 1 | 1 | 3 | 6 | 8 |
| 1 | 2 | 2 | 5 | 5 |
| 4 | 4 | 0 | 3 | 3 |
| 8 | 0 | 2 | 3 | 4 |
| 4 | 3 | 0 | 2 | 1 |
도달 실패!!
....
(7, 8)일 때 BFS 탐색 진행
| 1 | 1 | 3 | 6 | 8 |
| 1 | 2 | 2 | 5 | 5 |
| 4 | 4 | 0 | 3 | 3 |
| 8 | 0 | 2 | 3 | 4 |
| 4 | 3 | 0 | 2 | 1 |
도달 실패!!
start = mid + 1
다음 이분 탐색 진행
Start : 2
End : 3
mid = (2 + 3) ÷ 2 : 2
차이가 2일 때
나올 수 있는 경우의 수
{ (0, 2), (2, 4), (4, 6), (6, 8) }
(0, 2)일 때 BFS 탐색 진행
| 1 | 1 | 3 | 6 | 8 |
| 1 | 2 | 2 | 5 | 5 |
| 4 | 4 | 0 | 3 | 3 |
| 8 | 0 | 2 | 3 | 4 |
| 4 | 3 | 0 | 2 | 1 |
도달 성공!!
차이 2는 (1, 1) → (N, N)까지 도달할 수 있습니다.
end = mid - 1 : 1
result = Math.min(result, mid) : 2
이분 탐색 종료!!
3. 이분탐색을 통해 얻은 최소값을 결과로 출력합니다.
이분 탐색을 통해 최소값 : 2
2을 결과로 출력 합니다.
- BufferedReader를 사용하여 입력되는 정보를 저장합니다.
- StringTokenizer를 이용하여 배열의 정보를 띄어쓰기 기준 저장합니다.
- search함수를 통해서 차이의 최소값을 탐색합니다.
- 탐색을 통해 얻은 최소값을 BufferedWriter 저장합니다.
- BufferedWriter에 저장된 결과를 출력합니다.
- search함수는 이분탐색을 통해서 최소값과 최대값의 차이를 탐색합니다.
- bfs함수는 (1, 1) → (N, N) 도달하는지 BFS을 이용하여 확인합니다.
- bfs함수는 차이에 대한 모든 경우에 대해서 탐색을 진행합니다.
- inSpace함수는 이동하려는 칸이 배열에 존재하는지 확인합니다.
결과코드
import java.io.*;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
//BFS에서 배열의 위치 정보 관련 클래스
static class Info{
int r, c;
public Info(int r, int c){
this.r = r;
this.c = c;
}
}
static int[][] map; // 입력 배열 저장 배열
static int[] dr = {-1, 1, 0, 0}; //상하좌우 행 변경값
static int[] dc = {0, 0, -1, 1}; //상하좌우 열 변경값
public static void main(String[] args) throws IOException {
//입력값 처리하는 BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//결과값 출력하는 BufferedWriter
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
StringTokenizer st;
int max = -1;
int min = 201;
map = new int[N][N];
//입력값 저장
for(int i=0;i<N;i++){
st = new StringTokenizer(br.readLine()," ");
for(int j = 0;j<N;j++){
map[i][j] = Integer.parseInt(st.nextToken());
max = Math.max(max, map[i][j]); //최대값
min = Math.min(min, map[i][j]); //최소값
}
}
//이분탐색 진행
int result = search(max, min, N);
//최소값 BufferedWriter 저장
bw.write(String.valueOf(result));
bw.flush(); //결과 출력
bw.close();
br.close();
}
//이분 탐색을 통해 최소값을 찾는 함수
static int search(int max, int min, int N){
int start = 0;
int end = max - min;
int result = 201;
//이분 탐색 진행
while(start <= end){
//중간값 구하기
int mid = (start + end) / 2;
boolean flag = false;
//mid의 차이의 모든 경우 BFS 진행
for(int i = min; i+mid <= max; i++){
//범위 정보 설정
int s = i;
int e = i + mid;
//시작 위치 범위에 포함되는 지
if(map[0][0] >= s && map[0][0] <= e){
//BFS 진행
if(bfs(s, e, N)){ //(N, N) 도달 성공시
flag = true;
break;
}
}
}
//도달 성공
if(flag){
end = mid-1;
result = Math.min(result, mid);
}else{ //도달 실패
start = mid+1;
}
}
return result;
}
//BFS을 진행하는 함수
static boolean bfs(int s, int e, int N){
Queue<Info> q = new ArrayDeque<>();
boolean[][] visited = new boolean[N][N];
//시작값 저장
q.add(new Info(0, 0));
visited[0][0] = true;
//BFS 진행
while(!q.isEmpty()){
Info cur = q.poll();
//(N, N) 도달시
if(cur.r == N-1 && cur.c == N-1){
return true;
}
//상하좌우 인접한 공간 탐색
for(int i=0;i<4;i++){
int nr = cur.r + dr[i];
int nc = cur.c + dc[i];
//s ≤ map[nr][nc] ≤ e 범위에 포함되는 기준으로 탐색
if(inSpace(nr, nc, N) && !visited[nr][nc] && map[nr][nc] >= s && map[nr][nc] <= e){
q.add(new Info(nr, nc));
visited[nr][nc] = true;
}
}
}
return false;
}
//이동하려는 칸이 배열에 존재하는 칸인지 확인하는 함수
static boolean inSpace(int r, int c, int N){
//존재할 때
if(r >= 0 && r < N && c >= 0 && c < N){
return true;
}
return false;
}
}'백준' 카테고리의 다른 글
| [백준, Java] 12991번, 홍준이의 행렬(이분탐색) (0) | 2023.12.09 |
|---|---|
| [백준, Java] 1497번, 기타콘서트(백트래킹) (0) | 2023.12.09 |
| [백준, Java] 13505번, 두 수 XOR(트라이, 누적합) (2) | 2023.12.02 |
| [백준, Java] 27281번, 운전병의 딜레마(다익스트라, 이분탐색) (2) | 2023.11.19 |
| [백준, Java] 1726번, 로봇(다익스트라) (2) | 2023.11.11 |
댓글