๋ฌธ์
์ผ์์ผ ์์นจ์ ๋ฐ์ดํธ ์ฑ๊ณต
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;
}