문제
지문
- n*m크기 맵
- 출발점~도착점까지의 최소 난이도 구하기
- 이동 1. 좌-우 : 바로 옆 칸으로 이동 가능
- 이동 2. 상-하 : 이동 제한 없음.
- 난이도 = 상-하 이동 거리 중 최댓값
- ex) 0번 행 -> 3번 행 이동 + 1번 행 -> 2번 행 이동 = 난이도 3
예시
위와 같은 맵의 난이도 = 2
입력
0 : 빈 공간 = 이동 불가
1 : 발판
2 : 시작점
3 : 도착점
문제 정리
출발점부터 도착점까지 루트 중 상-하 이동 거리가 최솟값일 때의 값
.
이동 규칙
1. 좌-우 이동
- (r,c) -> (r,c+-1)
- 조건 : 이동할 칸이 1 또는 3
- 상-하 이동
- (r,c) -> (r+-x,c)
- 같은 열이라면 가장 가까운 발판까지 점프
- 점프 조건
- 0 통과 가능
- 1 or 3으로 이동
- 점프 거리 = 난이도
추가 힌트
해당 문제 지문에는 다음과 같은 힌트 또한 주어졌음
이 문제는 난이도를 정하고, 해당 난이도에서 해결이 가능한지 검사하는 방법도 존재한다.
즉, 점프 거리의 max값을 정해두고 움직일 수 있는지 여부 파악하는 방식으로 풀이 가능
=> 난이도(점프 거리)를 정한 후 for문 내부에서 BFS로 풀기를 선택
아이디어
변수 설정
int n, m; //격자크기 n,m
int ans; //정답 (난이도) ans
int startR, startC; //시작점(값 2) 좌표
int endR, endC; //도착점(값 3) 좌표
int[][] map; //암벽 정보 저장
boolean[][] visited; //bfs 방문처리용 배열
로직
한 지점에서 다른 지점까지의 최소 가중치? 다익스트라인가? 싶었지만 감이 안와서 추가 힌트대로 하나씩 탐색하며 BFS로 접근
난이도 최댓값 = 허용하는 최대 세로 이동 거리 = n-1
난이도(level)를 1부터 증가시키며 BFS 수행for(int level = 1;level<n;level++){ bfs(); }즉, 현재 상-하로 이동하는 거리를 제한했을 때 시작점~도착점 경로가 이어지는지 탐색
코드
전체 코드
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 test2 {
static int n, m, ans, startR, startC, endR, endC;
// 격자 크기 n,m / 정답 난이도 ans / 시작점 startR,startC / 도착점 endR,endC
static int[][] map;
static boolean[][] visited;
static int[] dr = { -1, 1, 0, 0 };
static int[] dc = { 0, 0, -1, 1 };
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int T = Integer.parseInt(st.nextToken());
for (int tc = 1; tc <= T; tc++) {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
map = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] == 2) {
startR = i;
startC = j;
} else if (map[i][j] == 3) {
endR = i;
endC = j;
}
}
}
// 입력 끝
ans = -1;
for (int level = 1; level < n; level++) {
visited = new boolean[n][m];
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[] { startR, startC });
visited[startR][startC] = true;
while (!q.isEmpty()) {
int[] temp = q.poll();
int r = temp[0];
int c = temp[1];
if (r == endR && c == endC) {
ans = level;
break;
}
for (int d = 0; d < 4; d++) {
if (d == 2 || d == 3) { // 좌우
int nr = r;
int nc = c + dc[d];
if (nr < 0 || nr >= n || nc < 0 || nc >= m || visited[nr][nc] || map[nr][nc] == 0)
continue;
visited[nr][nc] = true;
q.add(new int[] { nr, nc });
} else { // 상하
for (int i = 1; i <= level; i++) {
int nr = r + dr[d] * i;
int nc = c;
if (nr < 0 || nr >= n )
break;
if(map[nr][nc]==0) continue;
if(!visited[nr][nc]) {
visited[nr][nc] = true;
q.add(new int[] { nr, nc });
}
break; // 가장 가까운 발판만 이동 가능 . 방문이랑 상관없이 발판 만나면 종료
}
}
}
}
if (ans == level)
break;
}
System.out.println("#" + tc + " " + ans);
} // tc끝
}// main 끝
}
상세 코드
시작점, 도착점 저장
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] == 2) {
startR = i;
startC = j;
} else if (map[i][j] == 3) {
endR = i;
endC = j;
}
}
}난이도별 경로 탐색
for (int level = 1; level < n; level++) { ...}for문 내부 > 시작점으로부터 이어질 수 있는 위치 판별 = BFS
visited = new boolean[n][m];
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[] { startR, startC });
visited[startR][startC] = true;
while (!q.isEmpty()) {
int[] temp = q.poll();
int r = temp[0];
int c = temp[1];
if (r == endR && c == endC) {
ans = level;
break;
}
for (int d = 0; d < 4; d++) { ...}}
- 상하좌우 로 옮길 수 있으므로 델타배열로 이동 탐색.
- 좌-우 / 상-하 일 때 난이도 계산 법이 다르므로 각각 나눠 계산
BFS 내부 > 좌-우 이동
for (int d = 0; d < 4; d++) {
if (d == 2 || d == 3) { // 좌우
int nr = r;
int nc = c + dc[d];
if (nr < 0 || nr >= n || nc < 0 || nc >= m || visited[nr][nc] || map[nr][nc] == 0)
continue;
visited[nr][nc] = true;
q.add(new int[] { nr, nc });
}
- 좌, 우 이동 시 {r,c} -> {r, c+-1}로 이동 가능
- 난이도에 영향 없으므로 고려사항 X
BFS 내부 > 상-하 이동
else { // 상하
for (int i = 1; i <= level; i++) {
int nr = r + dr[d] * i;
int nc = c;
if (nr < 0 || nr >= n )
break;
if(map[nr][nc]==0) continue;
if(!visited[nr][nc]) {
visited[nr][nc] = true;
q.add(new int[] { nr, nc });
}
break; // 가장 가까운 발판만 이동 가능 . 방문이랑 상관없이 발판 만나면 종료
}
}
}
- 상, 하 이동 시 {r,c} -> {r+-x,c}로 이동 가능
- 이 때 x값 -> for문의 난이도(level)로 제한
- 즉, 상, 하로 이동 가능하지만, 이동 가능한 최댓값은 현재 난이도(level)
- 범위체크
if (nr < 0 || nr >= n ) break;
- 칸 탐색
if(map[nr][nc]==0) continue;: 해당 칸이 0인 경우 = 빈 칸 -> 도달할 수 없지만 건너뛸 수 있으므로 다음 칸 계속 확인
- 도달 가능하며(1 or 3) && 아직 방문하지 않은 칸
if(!visited[nr][nc]) { visited[nr][nc] = true; q.add(new int[] { nr, nc }); }: 발판/도착점에 도착했다면 큐에 넣음
- 규칙
break;: 가장 가까운 발판만 이동 가능 = 방문 여부와 관련 없이 가장 가까운 발판에 도달했다면 break 필요
ex)(위) 1 ← 거리 3 (멀다) 1 ← 거리 2 (가장 가까움) 0 현재의 경우에서, 거리 2인 발판이 이미 visited라고 하더라도 건너뛰고 갈 수 없음. 무조건 break 필요
정리
- 상-하 이동 처리와 종료 시점 처리(break 위치) 가 까다롭다고 느껴졌다.
- 시험 볼 당시 긴장되어 가중치 처리/상-하 이동 처리 로직에 대한 해답을 찾지 못했다.
- 여유를 가지고 다시 풀어보니 아이디어가 생각나 굉장히 아쉬웠다.
- GPT피셜 백준 골드 3-4정도
다른 풀이 방식
다익스트라
import java.io.*;
import java.util.*;
public class Main {
static int n, m;
static int[][] map;
static int[][] dist;
static int sr, sc, er, ec;
static final int INF = 987654321;
// 상 하 좌 우
static int[] dr = {-1, 1, 0, 0};
static int[] dc = {0, 0, -1, 1};
static class Node implements Comparable<Node> {
int r, c, cost;
Node(int r, int c, int cost) {
this.r = r;
this.c = c;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return this.cost - o.cost;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for (int tc = 1; tc <= T; tc++) {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
map = new int[n][m];
dist = new int[n][m];
for (int i = 0; i < n; i++) {
Arrays.fill(dist[i], INF);
}
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] == 2) {
sr = i;
sc = j;
} else if (map[i][j] == 3) {
er = i;
ec = j;
}
}
}
int answer = dijkstra();
sb.append("#").append(tc).append(" ").append(answer).append("\n");
}
System.out.print(sb);
}
static int dijkstra() {
PriorityQueue<Node> pq = new PriorityQueue<>();
dist[sr][sc] = 0;
pq.offer(new Node(sr, sc, 0));
while (!pq.isEmpty()) {
Node cur = pq.poll();
int r = cur.r;
int c = cur.c;
int cost = cur.cost;
if (cost > dist[r][c]) continue;
// 도착하면 바로 반환 (최소 보장)
if (r == er && c == ec) {
return cost;
}
for (int d = 0; d < 4; d++) {
// 상하 이동 (점프)
if (d == 0 || d == 1) {
for (int jump = 1; ; jump++) {
int nr = r + dr[d] * jump;
int nc = c;
if (nr < 0 || nr >= n) break;
// 발판 찾기
if (map[nr][nc] == 1 || map[nr][nc] == 3) {
int nextCost = Math.max(cost, jump); //최대값을 가져감
if (dist[nr][nc] > nextCost) {
dist[nr][nc] = nextCost;
pq.offer(new Node(nr, nc, nextCost));
}
break; // 가장 가까운 발판만
}
}
}
// 좌우 이동
else {
int nr = r;
int nc = c + dc[d];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
if (map[nr][nc] == 1 || map[nr][nc] == 3) {
int nextCost = cost;
if (dist[nr][nc] > nextCost) {
dist[nr][nc] = nextCost;
pq.offer(new Node(nr, nc, nextCost));
}
}
}
}
}
return -1;
}
}