29348번 Скользкий путь

문제

---

29348번 Скользкий путь - 백준

설계

---

앗 러시아어 문제
번역기의 힘을 빌리자…

루크 스카이워커가 어쩌고 하는데 집어치우고 문제의 요지를 파악해야한다.
정사각형으로 이루어진 맵에서 최단 경로를 찾아야하는 문제이다.

이동 조건은 아래와 같다.

• 지형은 건물, 눈, 얼음 3가지로 이루어져 있으며 칸마다 높이가 존재함
• 일반 이동 조건은 아래와 같음
  • 건물과 건물은 자유롭게 이동 가능
  • 건물과 눈은 자유롭게 이동 가능
  • 눈과 눈은 고도가 같거나 낮아야 이동 가능
  • 눈과 얼음은 고도가 같거나 낮아야 이동 가능
  • 얼음과 얼음 고도가 같거나 낮아야 이동 가능
• 특수 이동조건으로 미끄러짐이 존재함
  • 얼음에서 고도가 낮은 얼음으로 가면 미끄러지기 시작
  • 다음 칸이 눈이거나 고도가 높은 얼음, 맵 끝이라면 멈춤
  • 만약 건물을 만나면 충돌해서 실패하는 경로

출발점에서 도착점까지 최단 경로(칸 수)를 찾아야하며 경로가 존재하지 않으면 Impossible을 출력해야한다.

문제가 좀 머리아픈데…
잘못 걸린 것 같다.

단순히 생각하면 BFS 전략을 통해 최단거리를 찾으면 될 것 같긴 한데
미끄러지는 특수 이동이 문제다.
이거 미끄러지는게 미끄러지는 동안 1칸으로 취급되는건지, 미끄러지는 동안 그 칸을 모두 세어야하는건지…

이 망할 문제 푼 사람도 없어서 모르겠다.
만약 미끄러지는 구간 전체가 1칸으로 취급하는 것 보다 미끄러지는 모든 칸을 세는게 더 코드 짜기 쉬울 것 같아서 그렇게 짜보자.
틀리면 수정해야지.

BFS로 짜보자.

구현

---

1. 입력 받기

입력 받아서 큐는 초기화 진행한다.

int ar, ac, br, bc; // 시작점과 도착점 좌표
cin >> n >> m;
cin >> ar >> ac >> br >> bc;
ar--; ac--; br--; bc--;

// 맵에 지형 정보 입력
map.resize(n); 
for (int i = 0 ; i < n ; i++) {
    cin >> map[i];
}

// 높이 정보 입력
height.assign(n, vector<int>(m));
for (int i = 0 ; i < n ; i++) {
    for (int j = 0 ; j < m ; j++) {
        cin >> height[i][j];
    }
}

// 방문 거리 정보 초기화 (-1은 미방문, 방문 시 거리 저장)
visited.assign(n, vector<int>(m, -1)); 

que.push({ar, ac}); // 시작점 삽입
visited[ar][ac] = 0; // 시작점 거리: 0

2. BFS 루프

미끄러지는 특수이동 때문에 경로를 전체 탐색해야한다.
도착점 도달 결과가 없으면 Impossible, 있다면 저장된 거리 수를 출력한다.

while (!que.empty()) {
    int x, y;
    x = get<0>(que.front());
    y = get<1>(que.front());

    que.pop(); // 현재 위치

    int d = visited[x][y]; // 현재까지 거리

    for (int dir = 0; dir < 4; ++dir) { 
        // 탐색 로직
    }
}

// 도착점까지 도달했는지 확인
if (visited[br][bc] < 0){
    cout << "Impossible";
} else{
    cout << visited[br][bc];
}

3. 이동 조건 분기

루프 내부에 이동조건 분기를 만들어야한다.

• 건물
  • 건물 <-> 건물: 자유롭게 이동
  • 건물 -> 눈: 이동 가능
  • 건물 <- 눈: 이동 가능
• 눈
  • 눈 -> 눈: 높이가 작거나 같을 경우만 가능
  • 눈 -> 얼음: 높이가 작거나 같을 경우만 가능
  • 눈 <- 얼음: 높이가 작거나 같을 경우만 가능
• 얼음
  • 얼음 -> 눈: 높이가 작거나 같을 경우만 가능
  • 얼음 -> 얼음 (동일한 높이): 이동 가능
  • 얼음 -> 얼음 (낮은 높이): 미끄러짐 시작
    • 정지 조건
      • 눈 만남
      • 더 높은 얼음 만남
      • 지도 경계
  • 얼음 -> 건물: 충돌로 무조건 실패 (Impossible)

헷갈려서 계속 틀린 상황

• 눈에서 얼음갈때 높이 조건이 =< 인지 < 인지 체크
• 눈과 눈 이동도 높이 체크 필요
• 얼음에서 이동할때 높이 제대로 체크
• 얼음에서 얼음 갈때 높이 같으면 미끄러지는거 아님
• 미끄러질때 개박살 조건인 건물 반드시 체크
• 건물에서 얼음으로 가는 경우는 조건에 주어져 있지 않음
• 어떤 상황에서든 지도 경계 고려

얼음에서 미끄러지는 건 제외하고 나머지를 구현한다.

int nx = x + dx[dir], ny = y + dy[dir]; // 다음 위치

// 맵 범위 벗어나면 continue
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

char now = map[x][y], next = map[nx][ny];
int nowHeight = height[x][y], nextHeight = height[nx][ny];

if (now == 'B' && (next == 'B' || next == 'S')) {
    // 건물에서 건물 또는 눈으로 이동
    update(nx, ny, 1, d);
} else if (now == 'S') {
    // 눈에서 이동
    if (next == 'B' || ((next == 'S' || next == 'I') && nextHeight <= nowHeight))
        // 건물이거나 높이 확인
        update(nx, ny, 1, d);
} else if (now == 'I') {
        // 얼음에서 이동 (건물은 박살나니까 고려 안함)
    if (next == 'S' && nextHeight <= nowHeight){
        // 눈으로 이동
        update(nx, ny, 1, d);
    } else if (next == 'I') {
        // 얼음이면
        if (nextHeight == nowHeight){
            // 높이 같으면 이동
            update(nx, ny, 1, d);
        } else if (nextHeight < nowHeight) {
            // 미끄러지는 로직
        }
    }
}

4. 미끄러짐

미끄러질 경우 이동 방향으로 멈출때까지 전진한다.
멈추는 조건까지 전진하며 거리를 채우고 건물에 박는 경로는 폐기한다.
미끄러지는 동안은 while문으로 끝날 때까지 반복한다.

예제를 테스트 해보면 미끄러질 경우 지나간 칸 만큼 거리로 쳐주기 때문에 칸 수를 정확하게 체크해야한다.
건물에 부딪히면 박살나기 때문에 경로 폐기를 위한 불 값을 마련해준다.

정지 조건에 맞춰 정지했을 경우에 도착지점과 미끄러진 거리를 업데이트한다.
미끄러지는 도중은 정상적인 착지가 아니라 의미 없으므로 visited 갱신을 하지 않는다.

// 미끄러지기 시작
int slide = 1; // 이동 거리
bool isBuilding = false; // 건물 충돌 박살 여부
int ox = x, oy = y;

// 계속 미끄러지기
while (true) {
    if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
        // 맵 벗어나면 멈춤
        break; 
    }
    if (map[nx][ny] == 'B') { 
        // 건물 부딪히면 상태 업데이트하고 break
        isBuilding = true; 
        break; 
    } 
    if (map[nx][ny] != 'I' || height[nx][ny] > height[ox][oy]){
        // 얼음이 아니고 높이가 높으면 정지
        break; 
    } 

    ox = nx; 
    oy = ny; 
    nx += dx[dir]; 
    ny += dy[dir];

    slide++;
}

// 멈췄으면 실제 멈춘 위치로 보정
nx -= dx[dir]; 
ny -= dy[dir]; 
slide--;

// 맵 범위, 건물 체크
if ((nx < 0 || ny < 0 || nx >= n || ny >= m) || (map[nx][ny] == 'B')) {
    continue;
}

// 정상적으로 멈추면 업데이트
if (!isBuilding && map[nx][ny] != 'B') {
    update(nx, ny, slide, d);
}

채점

---

거지같은 문제 내가 해냈어 해냈다구

반성

---

계속 틀려서 BFS가 아니라 다익스트라에 가까워졌다.
미끄러지는 부분 고려하는게 너무 어려웠다.

아무래도 컨텐츠 잘못 만든 것 같다.
너무 지독한 문제에 걸려 오래 고생했다.
좀 쉬어야겠다.

코드 확인

---

Link to GitHub