BOJ 1445

10 Mar 2020 • ProblemSolving

일요일 아침의 데이트

문제출처

문제 해석

  • 형택이와 여자친구가 S에서 F로 가는 도중에, 쓰레기가 있는 곳을 최대한 피하면서 갈수 있는 경우를 구하는 문제입니다.
  • 쓰레기로 차있는 칸을 되도록이면 적게 지나가야 합니다.
  • 만약 해당 조건이 같은 경로가 여러개이면, 쓰레기 옆을 최소로 지나가야 합니다.
  • 이때, 쓰레기 옆이란 인접한 칸 즉, 상하좌우를 의미합니다.

설계(10)

  • 문제의 지문 중 애매한 부분이 많았던 bfs문제였습니다.
  • 먼저, 카운팅해야하는 조건중에 두번째 조건,”인접한 칸에 쓰레기가 있는 경우”는 상하좌우인지 8칸 전부를 조사해야하는지 정확히 명시가 되지 않아서 실험적으로 구현하였습니다. (먼저 4방향 체크를 해보고, 안되면 8방향을 하려고 했습니다.)
  • 결과적으로 4방향을 체크하면 되었습니다.
  • 두번째로, “S와 F는 세지 않는다”라는 지문이 있는데, S 또는 F칸의 인접한 칸에 쓰레기가 있는 경우가 있을 수 있습니다. 이러한 경우, 카운트 하지 않도록 구현하라는 것으로 이해하였습니다.
  • 만약 이동할 칸이 g이고 주변에 g가 있으면, 어떻게 해야할지도 생각해 보았습니다.
  • 쓰레기로 차있는 경우와 쓰레기 옆을 지나가는 경우 둘중의 하나를 카운트해야하는 것으로 이해하였습니다.
  • 두가지 조건의 우선순위가 있기 때문에, 우선순위큐를 사용하였습니다.

구현(10)

코드
#include <iostream>
#include <queue>
using namespace std;
#define MAXN 50
struct node{
    int x;
    int y;
    int g_cnt;
    int cnt;
    bool operator < (const node& a) const{
        if (a.g_cnt <=g_cnt){
            if (a.g_cnt == g_cnt) return a.cnt < cnt;
            return true;
        }
        return false;
    }
};

char map[MAXN][MAXN];
bool visited[MAXN][MAXN];
int N,M;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

priority_queue<node> pq;
bool is_range(int x,int y){
    return (x>=0 && y>=0 && x<N && y <M);
}
pair<int,int> bfs(){
    while (!pq.empty()){
        int x = pq.top().x;
        int y = pq.top().y;
        int g_cnt = pq.top().g_cnt;
        int cnt = pq.top().cnt;
        pq.pop();
        if (map[x][y] =='F'){
            return {g_cnt,cnt};
        }
        for (int i = 0 ; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (!is_range(nx,ny)) continue;
            if (visited[nx][ny]) continue;
            visited[nx][ny] = true;
            if (map[nx][ny]=='g'){
                pq.push({nx,ny,g_cnt+1,cnt});
            }
            else if (map[nx][ny] == '.'){
                bool flag = false;
                for (int k = 0 ;k <4; k++){
                    int nx1 = nx + dx[k];
                    int ny1 = ny + dy[k];
                    if (!is_range(nx1,ny1)) continue;
                    if (map[nx1][ny1] =='g') {
                        flag = true;
                        break;
                    }
                }
                if (flag) pq.push({nx,ny,g_cnt,cnt+1});
                else pq.push({nx,ny,g_cnt,cnt});
            }
            else{
                pq.push({nx,ny,g_cnt,cnt});
            }
        }
    }
}
int main(){
    scanf("%d%d",&N,&M);
    for (int i = 0; i< N; i++){
        for (int j = 0;j < M; j++){
            scanf(" %1c",&map[i][j]);
            if (map[i][j] =='S') {
                pq.push({i,j,0,0});
                visited[i][j]= true;
            }
        }
    }
    pair<int,int> ans = bfs();
    printf("%d %d",ans.first,ans.second);
    return 0;
}
디버깅
제출결과
  • 0ms

마무리

  • bfs탐색문제였습니다. 문제를 풀이하다보면, 문제의 지문이 깔끔하지 않은 경우가 많습니다. 이를 이해하기 애매한 경우가 많아서 꼼꼼히 읽지 않으면 틀리기 쉽상이니 주의해야겠습니다.
 BOJ

Related Posts