


백준 2589 보물섬
백준 2589 보물섬
2022년 11월 27일
2022년 11월 27일
cpp, 탐색
문제
문제
풀이
풀이
l,w의 값이 작아서 단순히 모든 칸을 시작점으로 삼아 제일 긴 목적지까지의 거리를 ans값으로 갱신해주면 해결 가능하다.
코드
코드
#include <bits/stdc++.h>
using namespace std;
int l,w,ans;
char board[52][52];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> l >> w;
for(int i=0; i<l; ++i)
for(int j=0; j<w; ++j)
cin >> board[i][j];
queue<pair<int,int>> q;
for(int i=0; i<l; ++i)
for(int j=0; j<w; ++j){
if(board[i][j] == 'W') continue;
int dist[52][52] = {0,};
dist[i][j] = 1;
q.push({i,j});
while(!q.empty()){
auto cur = q.front(); q.pop();
ans = max(ans,dist[cur.first][cur.second]);
for(int dir=0; dir<4; ++dir){
int nx = cur.first + dx[dir];
int ny = cur.second + dy[dir];
if(nx<0||ny<0||nx>=l||ny>=w) continue;
if(board[nx][ny] == 'W' || dist[nx][ny]) continue;
dist[nx][ny] = dist[cur.first][cur.second] + 1;
q.push({nx,ny});
}
}
}
cout << ans-1;
}
결과
결과

Copyright © 2024 Hyunghoon Kim