[Baekjoon] 2589번 보물섬

https://www.acmicpc.net/problem/2589

2589번: 보물섬

처음 풀때 DFS로 시도했었는데.. 최단거리를 구하는 문제라서 BFS로 풀어야 했다.. 처음부터 다시 풀었다,,,ㅠㅠ

 

i=0, j=0부터 시작해서 treasure[i][j] = 'L' 인 경우에, 해당 위치에서 제일 먼 L까지 최단거리를 하나씩 다 구해주고, 그중에서 제일 큰 값을 Max에 넣어 출력해줬다.

최단거리는 i와j값을 q에 push하고, 해당 위치에서 상 하 좌 우 로 움직일 수 있는 곳으로 계속 push해주면서 가장 먼 곳까지 갔을때의 거리를 cnt[i][j]에 넣어줬다. isVisited로 이미 방문한 위치는 재방문하지 않게 해줬다. 

 

 

 

 

처음 풀었던 코드

#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
#define SIZE 52

int L = 0;
int cnt[SIZE][SIZE];
bool isVisitied[SIZE][SIZE];
int Max = 0;
int x,y;
void init(){
    for(int i=0;i<SIZE;i++)memset(isVisitied[i], false , SIZE);
}
void BFS(vector<string> treasure, int N, int M){
    queue<pair<int, int>> q;

    for(int i=0;i<N;i++) for(int j=0;j<M;j++){
            if(treasure[i][j] == 'L') {
                init();
                q.push(make_pair(i, j));
                isVisitied[i][j] = true;
                while(!q.empty()){
                    int q_num = q.size();
                    for(int k=0;k<q_num;k++){
                        x = q.front().first;
                        y = q.front().second;
                        q.pop();
                    
                        if(y+1 < M && treasure[x][y+1] == 'L' && !isVisitied[x][y+1]) {q.push(make_pair(x, y+1));  isVisitied[x][y+1] = true;}
                        if(y-1 >= 0 && treasure[x][y-1] == 'L' && !isVisitied[x][y-1]) {q.push(make_pair(x, y-1));  isVisitied[x][y-1] = true;}
                        if(x+1 < N && treasure[x+1][y] == 'L' && !isVisitied[x+1][y]) {q.push(make_pair(x+1, y));  isVisitied[x+1][y] = true;}
                        if(x-1 >= 0 && treasure[x-1][y] == 'L' && !isVisitied[x-1][y]) {q.push(make_pair(x-1, y));  isVisitied[x-1][y] = true;}
                        
                    }
                    
                    if(q.empty()) break;
                    cnt[i][j]++;
                    if(Max < cnt[i][j]) Max = cnt[i][j];
                    
                }
            }
    }
  
}

int main(int argc, const char *argv[])
{

    int N,M;
    cin >> N >> M;
    vector<string> treasure(N);
    for(int i=0;i<N;i++) cin >> treasure[i];
    BFS(treasure, N, M);
    cout << Max;
    return 0;
}

 

 

수정한 코드 -> 좌표 이동부분 보기쉽게 수정

#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
#define SIZE 52

int L = 0;
int cnt[SIZE][SIZE];
bool isVisitied[SIZE][SIZE];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int Max = 0;
int x,y;
void init(){
    for(int i=0;i<SIZE;i++)memset(isVisitied[i], false , SIZE);
}
void BFS(vector<string> treasure, int N, int M){
    queue<pair<int, int>> q;

    for(int i=0;i<N;i++) for(int j=0;j<M;j++){
            if(treasure[i][j] == 'L') {
                init();
                q.push(make_pair(i, j));
                isVisitied[i][j] = true;
                while(!q.empty()){
                    int q_num = q.size();
                    
                    for(int k=0;k<q_num;k++){
                        x = q.front().first;
                        y = q.front().second;
                        q.pop();
                        
                        for(int k=0;k<4;k++){
                            int nx = x + dx[k];
                            int ny = y + dy[k];
                            if(nx >= 0 && ny >= 0 && nx < N && ny < M){
                                if(isVisitied[nx][ny] == false && treasure[nx][ny] == 'L'){
                                    q.push(make_pair(nx, ny));
                                    isVisitied[nx][ny] = true;
                                }
                            }
                        }
                                        
                    }
                    if(q.empty()) break;
                    cnt[i][j]++;
                    if(Max < cnt[i][j]) Max = cnt[i][j];
                }
            }
    }
  
}

int main(int argc, const char *argv[])
{

    int N,M;
    cin >> N >> M;
    vector<string> treasure(N);
    for(int i=0;i<N;i++) cin >> treasure[i];
    BFS(treasure, N, M);
    cout << Max;
    return 0;
}