런타임 에러때문에 고생좀 했다…

문제

  • 보물이 있는 섬에 대한 지도가 있다. 지도는 물을 나타내는 W와 육지를 나타내는 L로 구분되어 있으며 후크 선장은 L로만 다닐 수 있다. 보물은 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 당연하겠지만 최단 거리로 가기 위해서는 돌아가거나 같은 곳을 거치면 안 된다 ㅎ

입력

  • 첫째 줄에 지도의 세로, 가로 길이가 주어지며 그 후 L과 W로 표시된 지도가 입력으로 주어진다.

출력

예제 입력
5 7
WLLWWWL
LLLWLLL
LWLWLWW
LWLWLLL
WLLWLWW
예제 출력
8

접근

  • 딱봐도 BFS문제인데 어떻게 접근해야 할까?

내가 생각한 풀이

  • BFS를 어디서 어떻게 실행해야 할까?
    • 따로 주어진 시작점이 없으니 모든 점에서 연산은 해봐야 한다고 생각했음!
  • 최단 경로를 구하기 위해 각 지점에 도달할 수 있는 최단 거리를 저장하는 행렬을 만들어서 사용함.
    • 행렬에 저장함과 동시에 가장 긴 거리를 저장해놓은 maxdis의 값을 계속해서 갱신시켜줌.
  • for문이 모두 끝나면 원하는 값이 구해져 있을 것이다!

문제를 풀면서 힘들었던 점

  • 런타임 에러때문에 빡쳤던 문제… 배열의 범위보다 값이 초과할 경우 보통 런타임 에러가 뜬다. 그래서 처음엔 행렬의 범위를 51에서 52로 늘렸다. 그리고 0부터 시작이 아닌 1부터 시작으로 바꿨음에도 그대로 런타임 에러가 떴다… 이 문제를 풀 때 런타임 에러가 뜰만한 것은 잘못된 배열의 주소에 접근했을 때 밖에 없는데.. 뭐가 문제일까 고민하다가.. 예전에 파이썬으로 코딩할 때 무척 고생했던 기억이 떠올랐다. 그 당시 조건문에서 주소의 limit을 적지 않아서 계속 오류가 나던 것이 생각났고 if(map[yloc][xloc] == ‘L’ && chk(yloc,xloc) == 1 && check[yloc][xloc] == 0) 이렇게 되어있던 코드를 if(chk(yloc,xloc) == 1 && map[yloc][xloc] == ‘L’ && check[yloc][xloc] == 0) 이렇게 바꿨더니… 바로 맞았습니다가 등장했다.. 조건문의 순서의 중요성을 다시 한 번 깨닫는 순간이었다.

코드

#include<iostream>
#include<string>
#include<queue>
using namespace std;
struct xy{
  int y;
  int x;
};
string map[52];

int y,x,[4][2}] = {% {{1,0},{-1,0},{0,1},{0,-1}} %}, maxdis = 0;

bool chk(int a, int b){if(a>=0 && b>=0 && a<51 && b<51) return 1; else return 0;}
void doBFS(int y, int x){
  int check[52][52] = {0, }, count = 0, dis[52][52] = {0, };
  queue<struct xy> q;
  q.push({y,x});
  check[y][x] = 1;
  while(!q.empty()){
    struct xy temp = q.front();
    q.pop();
    for(int i = 0 ;i<4;i++){
      int yloc = temp.y + d[i][0], xloc = temp.x + d[i][1];
      if(chk(yloc,xloc) == 1 && map[yloc][xloc] == 'L' && check[yloc][xloc] == 0){
        q.push({yloc,xloc});
        check[yloc][xloc] = 1;
        dis[yloc][xloc] = dis[temp.y][temp.x] + 1;
        if(dis[yloc][xloc]>count) count = dis[yloc][xloc];
      }
    }
  }
  if(count>maxdis) maxdis = count;
}
int main(void){
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  cin>>y>>x;
  for(int i = 1 ;i<=y;i++) cin>>map[i];
  for(int i = 1 ;i<=y;i++){
    for(int j = 1 ;j<=x;j++){
      if(map[i][j] == 'L'){
        doBFS(i,j);
      }
    }
  }
  cout<<maxdis;
  return 0;
}