반응형
https://www.acmicpc.net/problem/2589
[문제풀이]
1.BFS로 풀수 있다.
2.L:육지로 이동가능한곳, W:물로 이동할 수 없다
3.L만 찾아서 1개씩 큐에 저장후 이동할 수 있는 가장 먼 거리를 찾는 문제이다.
4.map정보가 같은 크기의 visited배열을 만들어서 방문 기록을 하고 매번 초기화 해줘야한다.
#include <iostream>
#include <queue>
#include <memory.h>
using namespace std;
#define MAXN (50)
int N, M;//세로, 가로
char map[MAXN+10][MAXN+10];//지도정보
int visited[MAXN+10][MAXN+10];//방문 표시
struct Q{
int y,x,t;
};
int count=0,ans=-1;
int BFS(int y, int x,int t){
queue<Q>q;
int dy[]={-1,1,0,0};//동서남북
int dx[]={0,0,-1,1};
//1.초기화
count=0;
q={};
//2.큐에 초기값 저장
q.push({y,x,t});
//3.반복문
while(!q.empty()){
Q cur=q.front();q.pop();
visited[y][x]=1;
for(int i=0; i<4; i++){
t=cur.t;
int ny=cur.y+dy[i];
int nx=cur.x+dx[i];
if((ny<0) || (ny>=N) || (nx<0) || (nx>=M) || map[ny][nx]!='L') continue;
if(visited[ny][nx]==0){
visited[ny][nx]=1;
q.push({ny,nx,t+1});
count=t+1;
if(ans<count) ans=count;//ans에 최대값 업데이트
}
}
}
return ans;
}
void Solve(){
for (int i=0; i<N; i++){
for (int j=0; j<M; j++){
if(map[i][j]=='L'){
ans=BFS(i,j,0);
memset(visited,false,sizeof(visited));
}
}
}
cout<<ans<<endl;
}
void InputData(){
cin>>N>>M;
for (int i=0; i<N; i++){
cin>>map[i];
}
}
int main(){
InputData();
Solve();
return 0;
}반응형
'Algorithm > BFS,DFS' 카테고리의 다른 글
| [c++][백준]뱀과 사다리 (0) | 2022.05.16 |
|---|---|
| [C++][백준]1520 내리막길 (0) | 2022.04.10 |
| [C++][백준]14502 연구소 (0) | 2022.04.10 |
| [C++][백준]적록색약 (0) | 2022.04.10 |
| [c++][algoritm][baekjoon]7562 나이트의 이동 (0) | 2021.09.23 |
