๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๐Ÿ“ ์•Œ๊ณ ๋ฆฌ์ฆ˜/BOJ

[C++/BOJ] 17836 : ๊ณต์ฃผ๋‹˜์„ ๊ตฌํ•ด๋ผ! (์‹œ๋ฎฌ๋ ˆ์ด์…˜) / ์‚ฝ์งˆ ๊ธฐ๋ก

728x90

https://www.acmicpc.net/problem/17836

๋ฌธ์ œ

์šฉ์‚ฌ๋Š” ๋งˆ์™•์ด ์ˆจ๊ฒจ๋†“์€ ๊ณต์ฃผ๋‹˜์„ ๊ตฌํ•˜๊ธฐ ์œ„ํ•ด (N, M) ํฌ๊ธฐ์˜ ์„ฑ ์ž…๊ตฌ (1,1)์œผ๋กœ ๋“ค์–ด์™”๋‹ค. ๋งˆ์™•์€ ์šฉ์‚ฌ๊ฐ€ ๊ณต์ฃผ๋ฅผ ์ฐพ์ง€ ๋ชปํ•˜๋„๋ก ์„ฑ์˜ ์—ฌ๋Ÿฌ ๊ตฐ๋ฐ ๋งˆ๋ฒ• ๋ฒฝ์„ ์„ธ์›Œ๋†“์•˜๋‹ค. ์šฉ์‚ฌ๋Š” ํ˜„์žฌ์˜ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๋ฌด๊ธฐ๋กœ๋Š” ๋งˆ๋ฒ• ๋ฒฝ์„ ํ†ต๊ณผํ•  ์ˆ˜ ์—†์œผ๋ฉฐ, ๋งˆ๋ฒ• ๋ฒฝ์„ ํ”ผํ•ด (N, M) ์œ„์น˜์— ์žˆ๋Š” ๊ณต์ฃผ๋‹˜์„ ๊ตฌ์ถœํ•ด์•ผ๋งŒ ํ•œ๋‹ค.

๋งˆ์™•์€ ์šฉ์‚ฌ๋ฅผ ๊ดด๋กญํžˆ๊ธฐ ์œ„ํ•ด ๊ณต์ฃผ์—๊ฒŒ ์ €์ฃผ๋ฅผ ๊ฑธ์—ˆ๋‹ค. ์ €์ฃผ์— ๊ฑธ๋ฆฐ ๊ณต์ฃผ๋Š” T์‹œ๊ฐ„ ์ด๋‚ด๋กœ ์šฉ์‚ฌ๋ฅผ ๋งŒ๋‚˜์ง€ ๋ชปํ•œ๋‹ค๋ฉด ์˜์›ํžˆ ๋Œ๋กœ ๋ณ€ํ•˜๊ฒŒ ๋œ๋‹ค. ๊ณต์ฃผ๋‹˜์„ ๊ตฌ์ถœํ•˜๊ณ  ํ”„๋Ÿฌํฌ์ฆˆ ํ•˜๊ณ  ์‹ถ์€ ์šฉ์‚ฌ๋Š” ๋ฐ˜๋“œ์‹œ T์‹œ๊ฐ„ ๋‚ด์— ๊ณต์ฃผ๋‹˜์ด ์žˆ๋Š” ๊ณณ์— ๋„๋‹ฌํ•ด์•ผ ํ•œ๋‹ค. ์šฉ์‚ฌ๋Š” ํ•œ ์นธ์„ ์ด๋™ํ•˜๋Š” ๋ฐ ํ•œ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฐ๋‹ค. ๊ณต์ฃผ๋‹˜์ด ์žˆ๋Š” ๊ณณ์— ์ •ํ™•ํžˆ T์‹œ๊ฐ„๋งŒ์— ๋„๋‹ฌํ•œ ๊ฒฝ์šฐ์—๋„ ๊ตฌ์ถœํ•  ์ˆ˜ ์žˆ๋‹ค. ์šฉ์‚ฌ๋Š” ์ƒํ•˜์ขŒ์šฐ๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋‹ค.

 

์„ฑ์—๋Š” ์ด์ „ ์šฉ์‚ฌ๊ฐ€ ์‚ฌ์šฉํ•˜๋˜ ์ „์„ค์˜ ๋ช…๊ฒ€ "๊ทธ๋žŒ"์ด ์ˆจ๊ฒจ์ ธ ์žˆ๋‹ค. ์šฉ์‚ฌ๊ฐ€ ๊ทธ๋žŒ์„ ๊ตฌํ•˜๋ฉด ๋งˆ๋ฒ•์˜ ๋ฒฝ์ด ์žˆ๋Š” ์นธ์ผ์ง€๋ผ๋„, ๋‹จ์ˆจ์— ๋ฒฝ์„ ๋ถ€์ˆ˜๊ณ  ๊ทธ ๊ณต๊ฐ„์œผ๋กœ ๊ฐˆ ์ˆ˜ ์žˆ๋‹ค. "๊ทธ๋žŒ"์€ ์„ฑ์˜ ์–ด๋”˜๊ฐ€์— ๋ฐ˜๋“œ์‹œ ํ•œ ๊ฐœ ์กด์žฌํ•˜๊ณ , ์šฉ์‚ฌ๋Š” ๊ทธ๋žŒ์ด ์žˆ๋Š” ๊ณณ์— ๋„์ฐฉํ•˜๋ฉด ๋ฐ”๋กœ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค. ๊ทธ๋žŒ์ด ๋ถ€์ˆ  ์ˆ˜ ์žˆ๋Š” ๋ฒฝ์˜ ๊ฐœ์ˆ˜๋Š” ์ œํ•œ์ด ์—†๋‹ค.

์šฐ๋ฆฌ ๋ชจ๋‘ ์šฉ์‚ฌ๊ฐ€ ๊ณต์ฃผ๋‹˜์„ ์•ˆ์ „ํ•˜๊ฒŒ ๊ตฌ์ถœ ํ•  ์ˆ˜ ์žˆ๋Š”์ง€, ์žˆ๋‹ค๋ฉด ์–ผ๋งˆ๋‚˜ ๋นจ๋ฆฌ ๊ตฌํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ์•Œ์•„๋ณด์ž.

์ž…๋ ฅ

์ฒซ ๋ฒˆ์งธ ์ค„์—๋Š” ์„ฑ์˜ ํฌ๊ธฐ์ธ N, M ๊ทธ๋ฆฌ๊ณ  ๊ณต์ฃผ์—๊ฒŒ ๊ฑธ๋ฆฐ ์ €์ฃผ์˜ ์ œํ•œ ์‹œ๊ฐ„์ธ ์ •์ˆ˜ T๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ฒซ ์ค„์˜ ์„ธ ๊ฐœ์˜ ์ˆ˜๋Š” ๋„์–ด์“ฐ๊ธฐ๋กœ ๊ตฌ๋ถ„๋œ๋‹ค. (3 ≤ N, M ≤ 100, 1 ≤ T ≤ 10000)

๋‘ ๋ฒˆ์งธ ์ค„๋ถ€ํ„ฐ N+1๋ฒˆ์งธ ์ค„๊นŒ์ง€ ์„ฑ์˜ ๊ตฌ์กฐ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” M๊ฐœ์˜ ์ˆ˜๊ฐ€ ๋„์–ด์“ฐ๊ธฐ๋กœ ๊ตฌ๋ถ„๋˜์–ด ์ฃผ์–ด์ง„๋‹ค. 0์€ ๋นˆ ๊ณต๊ฐ„, 1์€ ๋งˆ๋ฒ•์˜ ๋ฒฝ, 2๋Š” ๊ทธ๋žŒ์ด ๋†“์—ฌ์žˆ๋Š” ๊ณต๊ฐ„์„ ์˜๋ฏธํ•œ๋‹ค. (1,1)๊ณผ (N,M)์€ 0์ด๋‹ค.

์ถœ๋ ฅ

์šฉ์‚ฌ๊ฐ€ ์ œํ•œ ์‹œ๊ฐ„ T์‹œ๊ฐ„ ์ด๋‚ด์— ๊ณต์ฃผ์—๊ฒŒ ๋„๋‹ฌํ•  ์ˆ˜ ์žˆ๋‹ค๋ฉด, ๊ณต์ฃผ์—๊ฒŒ ๋„๋‹ฌํ•  ์ˆ˜ ์žˆ๋Š” ์ตœ๋‹จ ์‹œ๊ฐ„์„ ์ถœ๋ ฅํ•œ๋‹ค.

๋งŒ์•ฝ ์šฉ์‚ฌ๊ฐ€ ๊ณต์ฃผ๋ฅผ T์‹œ๊ฐ„ ์ด๋‚ด์— ๊ตฌ์ถœํ•  ์ˆ˜ ์—†๋‹ค๋ฉด, "Fail"์„ ์ถœ๋ ฅํ•œ๋‹ค.


 

๊ณจ๋“œ5

๋ณต์žกํ•œ ์ถœ๋ ฅ ์˜ˆ์™ธ์ฒ˜๋ฆฌ๋•Œ๋ฌธ์— ๋ฐ˜๋‚˜์ ˆ์„ ํ—ค๋งจ ๋ฌธ์ œ.........

ใ„นใ…‡์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋™์•„๋ฆฌ ๋“ค๊ธธ ์ž˜ํ–ˆ๋‹ค

๋ฌผ์–ด๋ณผ ์ˆ˜ ์žˆ๋Š” ๋ฉ˜ํ† ๊ฐ€ ์žˆ๋‹ค๋Š”๊ฑด ์ •๋ง ์ข‹์€ ์ผ

 

์ค‘๊บพ๋งˆ^^ ,,,

 

๋ณต์žกํ•œ bfs ๋ฌธ์ œ์ธ๋“ฏํ•˜๋‹ค.

gram์„ ์–ป์ง€ ์•Š๋Š” ์ตœ๋‹จ๊ฑฐ๋ฆฌ์™€ gram์„ ์–ป์–ด์„œ ๊ฐ€๋Š” ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐ๊ฐ ๊ตฌํ•ด์„œ

์กฐ๊ฑด์— ๋งž๋Š” ์ตœ์†Ÿ๊ฐ’์„ ์ถœ๋ ฅ์‹œํ‚ค๋ฉด ๋œ๋‹ค

 

isgram ๊ฐ’์„ ๊ตฌํ• ๋•Œ end point๋ฅผ gram์˜ ์œ„์น˜๋กœ ์„ค์ •ํ•ด์„œ bfs๋ฅผ ๋Œ๋ฆฌ๊ณ ,

gram์— ๋„๋‹ฌํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์— ํ•œํ•ด์„œ gram๋ถ€ํ„ฐ ๊ณต์ฃผ๊นŒ์ง€์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๋”ํ•˜๋ฉด ๋จ

 

bfs ํ•œ๋ฒˆ์œผ๋กœ ๋๋‚ผ ์ˆ˜ ์žˆ๋Š” ์ตœ์ ํ™” ๋ฐฉ์•ˆ๋„ ๊ณ ๋ฏผํ•ด๋ณด์•„์•ผ๊ฒ ๋‹ค.

 

 

 

๋‚˜์˜ ํ’€์ด

#include <iostream>
#include <queue>
using namespace std;
// boj 17836
int n;
int m;
int t;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int map[101][101] = {0};
pair<int, int> gramPoint;

bool canGo(int visited[101][101], int x, int y, bool gram){
    if(x<1 || x>n || y<1 || y>m) return false;
    if(visited[x][y] == 1) return false;
    if(map[x][y] == 1){
        if(gram) return true;
        else return false;
    }
    return true;
}

int bfs(int sx, int sy, int ex, int ey, bool gram){ // ์ตœ๋‹จ๊ฑฐ๋ฆฌ
    int cnt[101][101] = {0};
    int visited[101][101] = {0};
    queue<pair<int, int>> q;
    q.push({sx, sy});
    visited[sx][sy] = 1;
    while(!q.empty()){
        pair<int,int> a = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i){
            int nx = a.first + dx[i];
            int ny = a.second + dy[i];
            
            if(canGo(visited, nx, ny, gram)){
                visited[nx][ny] = 1;
                q.push({nx, ny});
                cnt[nx][ny] = cnt[a.first][a.second] + 1;
                // cout << nx<<" "<<ny<<" " << cnt[nx][ny]<<"\n";
                if(nx==ex && ny==ey) {
                    // cout << cnt[nx][ny]<<"---\n";
                    return cnt[nx][ny];
                }
            }
        }
    }

    return 0;
}

int main(){
    cin >> n >> m >> t;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            cin >> map[i][j];
            if(map[i][j]==2){
                gramPoint = {i, j};
            }
        }
    }
    int nogram = bfs(1, 1, n, m, false);
    int isgram = bfs(1, 1, gramPoint.first, gramPoint.second, false);
    if(isgram!=0){
        isgram += bfs(gramPoint.first, gramPoint.second, n, m, true);
    }
    
    int mintime = min(nogram, isgram);

    if(nogram==0 && isgram==0) cout <<"Fail";
    else if(nogram==0 && isgram !=0 ) {
        if(isgram > t) cout <<"Fail";
        else cout << isgram;
    }
    else if(nogram!=0 && isgram ==0 ) {
        if(nogram > t) cout <<"Fail";
        else cout << nogram;
    }
    else if(mintime > t) cout <<"Fail";
    else cout << mintime;
    return 0;
}

 

728x90