algorithm

BOJ 1445

rkawk 2022. 10. 13. 18:11

๋ฌธ์ œ

๋”๋ณด๊ธฐ

์ผ์š”์ผ ์•„์นจ์˜ ๋ฐ์ดํŠธ ์„ฑ๊ณต

 
2 ์ดˆ 128 MB 3223 860 586 23.667%

๋ฌธ์ œ

์ผ์š”์ผ ์•„์นจ์— ํ˜•ํƒ์ด๋Š” Maroon5์˜ Sunday Morning์ด๋ž€ ๋…ธ๋ž˜๋ฅผ ๋“ค์œผ๋ฉด์„œ ์—ฌ์ž์นœ๊ตฌ์™€์˜ ๋กœ๋งจํ‹ฑํ•œ ์—ฌํ–‰์„ ๋– ๋‚˜๊ธฐ๋กœ ํ–ˆ๋‹ค. ํ˜•ํƒ์ด๋Š” ์ด๊ฒƒ์ €๊ฒƒ ํ™˜์ƒ์— ๋น ์ ธ์žˆ๋‹ค๊ฐ€, ๊ณ„ํš์„ ์„ธ์šฐ๋Š”๋ฐ ์‹คํŒจํ–ˆ๋‹ค. ๋”ฐ๋ผ์„œ, ์ฃผ์œ„์— ์žˆ๋Š” ์ˆฒ์„ ๊ฐ™์ด ํƒํ—˜ํ•˜๊ธฐ๋กœ ํ–ˆ๋‹ค.

๊นŠ์€ ์ˆฒ์†์—๋Š” ์ •๋ง ์•„๋ฆ„๋‹ค์šด ๊ฝƒ์ด ํ•˜๋‚˜์žˆ๋‹ค. ํ˜•ํƒ์ด๋Š” ์—ฌ์ž์นœ๊ตฌ์˜ ๋งˆ์Œ์„ ๊ฐ๋™์‹œํ‚ค๊ธฐ ์œ„ํ•ด์„œ, ๊ฝƒ์„ ๋ณด์—ฌ์ฃผ๋ฉด์„œ ์ž์‹ ์˜ ๋งˆ์Œ์„ ์ „ํ•ด์ฃผ๋ ค๊ณ  ๊ธ‰ํ•˜๊ฒŒ ๊ณ„ํšํ–ˆ๋‹ค.

๋ถˆํ–‰ํ•˜๊ฒŒ๋„, ์‚ฌ๋žŒ๋“ค์ด ์ˆฒ์—๋‹ค ์“ฐ๋ ˆ๊ธฐ๋ฅผ ๋ฒ„๋ ค์„œ ํ˜•ํƒ์ด์˜ ๊ณ„ํš์€ ์ •๋ง ๋ง๊ฐ€์ง€๊ธฐ ์ง์ „์ด๋‹ค.

ํ˜•ํƒ์ด๋Š” ๊ทธ๋™์•ˆ ์—ฌ์ž์นœ๊ตฌ์™€ ์‚ฌ๊ท€๋ฉด์„œ 2๊ฐ€์ง€ ๊นจ๋‹ฌ์€ ๊ฒƒ์ด ์žˆ๋Š”๋ฐ, ํ•œ ๊ฐ€์ง€๋Š” ์“ฐ๋ ˆ๊ธฐ๋ฅผ ํ†ต๊ณผํ•ด์„œ ์ง€๋‚˜๊ฐ€๋Š” ๊ฒƒ์„ ์ •๋ง ์‹ซ์–ดํ•˜๋Š” ๊ฒƒ์ด๊ณ , ์“ฐ๋ ˆ๊ธฐ๋ฅผ ๋”ฐ๋ผ ์˜†์„ ์ง€๋‚˜๊ฐ€๋Š” ๊ฒƒ๋„ ์ •๋ง ๋ถˆํŽธํ•˜๊ฒŒ ๋А๋‚€๋‹ค๋Š” ๊ฒƒ์ด๋‹ค.

ํ˜•ํƒ์ด๋Š” ๋ฐฉ๊ธˆ ์“ฐ๋ ˆ๊ธฐ๊ฐ€ ์–ด๋””์—์žˆ๋Š”์ง€ ์กฐ์‚ฌ๋ฅผ ๋งˆ์ณค๋‹ค. ์ž…๋ ฅ์œผ๋กœ ์ˆฒ์˜ ์ง€๋„๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. S๋Š” ํ˜•ํƒ์ด์™€ ์—ฌ์ž์นœ๊ตฌ์˜ ๋ฐ์ดํŠธ ์‹œ์ž‘์žฅ์†Œ๋ฅผ  ๋‚˜ํƒ€๋‚ด๊ณ , F๋Š” ๊ฝƒ์ด ์žˆ๋Š” ์œ„์น˜๋ฅผ ๋‚˜ํƒ€๋‚ด๊ณ , g๋Š” ์“ฐ๋ ˆ๊ธฐ๊ฐ€ ์žˆ๋Š” ์œ„์น˜๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค. ๊ทธ๋ฆฌ๊ณ  .์€ ์•„๋ฌด๊ฒƒ๋„ ์—†๋Š” ๊นจ๋—ํ•œ ์นธ์ด๋‹ค.

ํ˜•ํƒ์ด์˜ ๋ชฉํ‘œ๋Š” S์—์„œ F๊นŒ์ง€ ๊ฐ€๋Š”๋ฐ, ์“ฐ๋ ˆ๊ธฐ๋กœ ์ฐจ์žˆ๋Š” ์นธ์„ ๋˜๋„๋ก์ด๋ฉด ์ ๊ฒŒ ์ง€๋‚˜๊ฐ€๋Š” ๊ฒƒ์ด๋‹ค. ํ˜•ํƒ์ด์™€ ์—ฌ์ž์นœ๊ตฌ๋Š” ํ•œ ๋ฒˆ์— ํ•œ ์นธ ์›€์ง์ผ ์ˆ˜ ์žˆ๋‹ค. ๊ฐ€๋กœ or ์„ธ๋กœ๋กœ ํ•œ ์นธ ์›€์ง์ผ ์ˆ˜ ์žˆ๋‹ค. ๋งŒ์•ฝ ๋˜๋„๋ก ์ ๊ฒŒ ์ง€๋‚˜๊ฐ€๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ์—ฌ๋Ÿฌ๊ฐœ๋ผ๋ฉด, ์“ฐ๋ ˆ๊ธฐ ์˜†์„ ์ง€๋‚˜๊ฐ€๋Š” ์นธ์˜ ๊ฐœ์ˆ˜๋ฅผ ์ตœ์†Œ๋กœ ํ•ด์„œ ์ง€๋‚˜๋ ค๊ณ  ํ•œ๋‹ค. ๋งŒ์•ฝ ์–ด๋–ค ์นธ์ด ๋น„์–ด์žˆ๋Š”๋ฐ, ์ธ์ ‘ํ•œ ์นธ์— ์“ฐ๋ ˆ๊ธฐ๊ฐ€ ์žˆ์œผ๋ฉด ์“ฐ๋ ˆ๊ธฐ ์˜†์„ ์ง€๋‚˜๋Š” ๊ฒƒ์ด๋‹ค. ๊ทธ๋ฆฌ๊ณ , S์™€ F๋Š” ์„ธ์ง€ ์•Š๋Š”๋‹ค.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— ์ˆฒ์˜ ์„ธ๋กœ ํฌ๊ธฐ N๊ณผ ๊ฐ€๋กœ ํฌ๊ธฐ M์ด ์ฃผ์–ด์ง„๋‹ค. N๊ณผ M์€ 3๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 50๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ ์ˆฒ์˜ ์ง€๋„๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ˆฒ์˜ ์ง€๋„๋Š” S, F, g, . ๋งŒ์œผ๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. S๋Š” ๋ฐ˜๋“œ์‹œ ๋ชจ์„œ๋ฆฌ์— ์œ„์น˜ํ•ด ์žˆ๊ณ , F๋Š” ๋ชจ์„œ๋ฆฌ์— ์œ„์น˜ํ•ด์žˆ์ง€ ์•Š๋‹ค. ๊ทธ๋ฆฌ๊ณ  S์™€ F๋Š” ๋ฐ˜๋“œ์‹œ ํ•˜๋‚˜๋งŒ ์ฃผ์–ด์ง„๋‹ค.

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— ํ˜•ํƒ์ด์™€ ์—ฌ์ž์นœ๊ตฌ๊ฐ€ ๊ฐ€์žฅ ์ตœ์ ์˜ ๋ฐฉ๋ฒ•์œผ๋กœ ์ˆฒ์„ ์ง€๋‚ฌ์„ ๋•Œ, ์ง€๋‚˜๊ฐ€๋Š” ์“ฐ๋ ˆ๊ธฐ์˜ ์ตœ์†Œ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๊ณ , ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„ ํ•œ ํ›„์— ์“ฐ๋ ˆ๊ธฐ ์˜†์„ ์ง€๋‚˜๊ฐ€๋Š” ์นธ์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

์˜ˆ์ œ ์ž…๋ ฅ 1 ๋ณต์‚ฌ

6 6
......
g..F..
......
..g...
......
...S.g

์˜ˆ์ œ ์ถœ๋ ฅ 1 ๋ณต์‚ฌ

0 0โ€‹

ํ’€์ด

์™„์ „ํƒ์ƒ‰ ๊ธฐ๋ฐ˜ ๋ฌธ์ œ์ด๋‹ค.

N * M ์˜ charํ˜• ์ด์ฐจ์› ๋ฐฐ์—ด๋กœ ์ž…๋ ฅ์ด ์ฃผ์–ด์ง€๊ธฐ ๋•Œ๋ฌธ์— ๊ฐ๊ฐ์˜ ์นธ์€ ๋…ธ๋“œ๊ฐ€ ๋˜๊ณ , ์ด ๋…ธ๋“œ๋Š” ์ƒํ•˜์ขŒ์šฐ ์ „๋ถ€ ๊ฐ„์„ ์ด ์žˆ๋Š” ์ƒํƒœ์ด๋‹ค.

ํ•˜์ง€๋งŒ ํƒ์ƒ‰์„ ํ•˜๋Š” ๋„์ค‘์—, ์“ฐ๋ ˆ๊ธฐ๋ฅผ ๋” ์ ๊ฒŒ ์ง€๋‚˜๋Š” ๊ฒฝ์šฐ, ์“ฐ๋ ˆ๊ธฐ๋ฅผ ์ง€๋‚˜๋Š” ์นธ์˜ ๊ฐœ์ˆ˜๊ฐ€ ๊ฐ™์„๋•Œ, ์“ฐ๋ ˆ๊ธฐ ์ฃผ์œ„๋ฅผ ์ง€๋‚˜๋Š” ์นธ์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ฐฑ์‹ ํ•ด์ฃผ์–ด์•ผ ํ•œ๋‹ค. 

์ด ๋ชจ๋“  ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์‹œ์ž‘์ ์ด ์ •ํ•ด์ ธ์žˆ๊ณ , ์–ด์จŒ๋“  ์ตœ์†Œ๊ฐ’์„ ๊ฐฑ์‹ ํ•ด์ฃผ๋Š” ๊ณผ์ •์ด๊ธฐ ๋•Œ๋ฌธ์— ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค.

์“ฐ๋ ˆ๊ธฐ๋ฅผ ์ง€๋‚˜๋Š” ๊ฒฝ์šฐ๋Š” ์ด์ „๋…ธ๋“œ์˜ ์“ฐ๋ ˆ๊ธฐ๋ฅผ ์ง€๋‚˜๋Š” ๊ฐ’์— +1ํ•ด์ฃผ๊ณ , ๋นˆ์นธ์„ ์ง€๋‚˜๋Š” ๊ฒฝ์šฐ๋Š” ๊ทธ ์ฃผ์œ„(์ƒํ•˜์ขŒ์šฐ ๋…ธ๋“œ)๋ฅผ ํƒ์ƒ‰ํ•ด์ค€ ๋‹ค์Œ ์“ฐ๋ ˆ๊ธฐ์— ํ•ด๋‹น๋˜๋Š” ๊ฐ’์ด ์žˆ์œผ๋ฉด ์“ฐ๋ ˆ๊ธฐ ์ฃผ์œ„๋ฅผ ์ง€๋‚˜๋Š” ์นธ์˜ ๊ฐ’์— +1ํ•ด์ฃผ๋ฉด ๋œ๋‹ค.

 

์ž…๋ ฅ์„ ๋ฐ›์œผ๋ฉด์„œ ๋™์‹œ์— ์ถœ๋ฐœ์ง€์™€ ๋„์ฐฉ์ง€๋ฅผ ๋ฐ›๊ณ 

for(int i=0; i<N; i++){
        cin>>board[i];
        for(int j=0; j<M; j++){
            if(board[i][j] == 'S'){
                S.first = i; S.second = j;
            }
            if(board[i][j] == 'F'){
                F.first = i; F.second = j;
            }
        }
    }

pair<int,int>ํ˜• ๋ฐฐ์—ด์˜ ๊ฐ’์„ ๋ชจ๋‘ INF๋กœ ์ดˆ๊ธฐํ™”ํ•ด์ฃผ๊ณ 

pair<int,int>dist[51][51];
    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++){
            dist[i][j].first = INF;
            dist[i][j].second = INF;
        }

์‹œ์ž‘์ ์€ 0,0์œผ๋กœ ์ดˆ๊ธฐํ™” ํ•œ๋‹ค์Œ์— ํƒ์ƒ‰์„ ํ•˜๊ธฐ ์œ„ํ•œ queue์— ๋„ฃ์–ด์ฃผ๋ฉด ๋œ๋‹ค.

dist[S.first][S.second].first = 0;
dist[S.first][S.second].second = 0;
queue<pair<int,int>>q;
q.push(S);

๊ทธ ๋ฐ‘์˜ ๊ณผ์ •์€ ๋‹ค์ต์ŠคํŠธ๋ผ์™€ ๊ฐ™๊ณ , ์ตœ์†Ÿ๊ฐ’์„ ์ดˆ๊ธฐํ™” ํ•ด์ฃผ๋Š” ๋ถ€๋ถ„๋งŒ ์œ„์— ๊ธฐ์ˆ ํ•œ๋Œ€๋กœ ํ•ด์ฃผ๋ฉด ๋œ๋‹ค.

if(board[nx][ny] == 'g'){
                nxt_g += 1;
            }else if(board[nx][ny] == '.'){
                
                    for(int dir2 = 0; dir2<4; dir2++){
                        int nx2 = nx + dx[dir2];
                        int ny2= ny + dy[dir2];
                        if(nx2 < 0 || nx2 >= N || ny2 < 0 || ny2 >= M) continue;
                        if(board[nx2][ny2] == 'g'){
                            nxt_nxtg += 1;
                            break;
                        }
                    
                }
            }

 

์ฃผ์˜์ 

์‹œ์ž‘๋…ธ๋“œ์™€ ๋„์ฐฉ๋…ธ๋“œ๋Š” ์–ด๋– ํ•œ ๊ฒฝ์šฐ์—๋„ ๊ณ„์‚ฐ์— ํฌํ•จ๋˜์ง€ ์•Š๋Š”๋‹ค.

 

์ „์ฒด์ฝ”๋“œ

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#define INF 987654321
using namespace std;
int N, M,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
string board[51];
pair<int,int>S, F;
int main(){
    cin>>N>>M;
    for(int i=0; i<N; i++){
        cin>>board[i];
        for(int j=0; j<M; j++){
            if(board[i][j] == 'S'){
                S.first = i; S.second = j;
            }
            if(board[i][j] == 'F'){
                F.first = i; F.second = j;
            }
        }
    }
    pair<int,int>dist[51][51];
    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++){
            dist[i][j].first = INF;
            dist[i][j].second = INF;
        }
    dist[S.first][S.second].first = 0;
    dist[S.first][S.second].second = 0;
    queue<pair<int,int>>q;
    q.push(S);
    while(!q.empty()){
        auto cur = q.front();
        int cur_g = dist[cur.first][cur.second].first;
        int cur_nxtg = dist[cur.first][cur.second].second;
        q.pop();
        for(int dir = 0; dir<4; dir++){
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            int nxt_g = cur_g; int nxt_nxtg = cur_nxtg;
            if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if(board[nx][ny] == 'g'){
                nxt_g += 1;
            }else if(board[nx][ny] == '.'){
                
                    for(int dir2 = 0; dir2<4; dir2++){
                        int nx2 = nx + dx[dir2];
                        int ny2= ny + dy[dir2];
                        if(nx2 < 0 || nx2 >= N || ny2 < 0 || ny2 >= M) continue;
                        if(board[nx2][ny2] == 'g'){
                            nxt_nxtg += 1;
                            break;
                        }
                    
                }
            }
            if(dist[nx][ny].first > nxt_g){
                dist[nx][ny].first = nxt_g;
                dist[nx][ny].second = nxt_nxtg;
                q.push({nx,ny});
            }else if(dist[nx][ny].first == nxt_g && dist[nx][ny].second > nxt_nxtg){
                dist[nx][ny].second = nxt_nxtg;
                q.push({nx,ny});
            }
        }
    }
    // cout<<endl;
    // for(int i=0; i<N; i++){
    //     for(int j=0; j<M; j++){
    //         cout<<dist[i][j].first <<' '<<dist[i][j].second<<' ';
    //     }
    //     cout<<endl;
    // }
    cout<<dist[F.first][F.second].first<<' '<<dist[F.first][F.second].second;
}

'algorithm' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

BOJ 1976  (0) 2022.10.15
BOJ 17143  (1) 2022.10.13
BOJ 2056  (2) 2022.10.10
BOJ 5021  (0) 2022.10.10
BOJ 20056  (0) 2022.10.09