My Profile

김형훈

안녕하세요.
김형훈입니다.

백준 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