[백준] 2589 - 보물섬

 

2589번: 보물섬

✏️  풀이

가장 먼 거리를 구하는것이 이 문제의 핵심이였다. 하지만 한 지점에서만 구하는 것이 아니라 L있는 부분에서 가장 먼거리라서 2중 for문을 통해서 브루트 포스를 통해서 모든 거리를 구해 그중에 가장 먼 거리를 출력하는 것이다.

이번 문제는 c++를 익히기 위해서 두가지 언어로 풀었다. 처음에는 파이썬으로 풀어서 해결방법을 찾고, 그걸 바탕으로 c++을 이용해서 코드를 작성했다.

💻  코드

import sys
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split())
graph = [list(input().strip()) for _ in range(n)]

result = -1
dxs = [-1, 1, 0, 0]
dys = [0, 0, -1, 1]

for i in range(n):
  max_value = 0
  for j in range(k):
    if graph[i][j] == 'L':
      visited = [[0]*k for _ in range(n)]
      visited[i][j] = 1
      q = deque()
      q.append((i, j, 0))
      while q:
        x, y, cnt = q.popleft()
        max_value = max(max_value, cnt)
        for dx, dy in zip(dxs, dys):
          nx = x + dx; ny = y + dy
          if 0 <= nx < n and 0 <= ny < k and visited[nx][ny] == 0 and graph[nx][ny] == 'L':
            visited[nx][ny] = 1
            q.append((nx, ny, cnt+1))
  result = max(result, max_value)
print(result)

파이썬을 활용해서 풀었을때는 시간초과가 처음에 발생하여 다시 생각하여 조건을 추가해서 풀었다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#define MAX 50
using namespace std;

struct node{
	int x,y,cnt;
};

int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
char graph[MAX][MAX];
bool visited[MAX][MAX];
int n, k;

void input(){
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        string s; cin >> s;
        for(int j = 0; j < k; j++){
            graph[i][j] = s[j];
        }
    }
}

int bfs(int x, int y){
    queue<node> q;
    q.push({x, y, 0});     // q.push(make_pair(x, y)); 이렇게 써도 됨
    visited[x][y] = true;
    int max_value = -1;
    while(!q.empty()){
        node v = q.front(); q.pop();
        for(int i = 0; i < 4; i++){
            int nx = dir[i][0] + v.x;
            int ny = dir[i][1] + v.y;
            bool check_x = 0<=nx && nx < n;
            bool check_y = 0<=ny && ny < k;
            bool check_c = graph[nx][ny] == 'L'; // Fix: Change "L" to 'L'
            if (check_x && check_y && !visited[nx][ny] && check_c) {
                q.push({nx, ny, v.cnt+1});
                visited[nx][ny] = true;
                max_value = max(max_value, v.cnt+1);
            }
        }
    }
    return max_value;
}

int main(void){
    int result = -1;
    input();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < k; j++){
            if(graph[i][j] == 'L'){
                memset(visited, 0, sizeof(visited));
                result = max(result, bfs(i, j));
            }
        }
    }
    cout << result;
    return 0;
}

c++을 처음 사용하는 거라 파이썬이랑 많은 것이 달라 문법을 사용하는 것에 조금 어려움이 걸렸다.