글 읽기 - 2589 보물섬 도와주세요 (코드 주석 있음)

dogdriip 5년 전 0

맵의 모든 글자를 검사해서 L일 경우마다 그 자리에서 BFS를 돌려서, 섬 내의 가장 멀리 있는 L까지의 거리를 저장했습니다. 이 최장거리들 중 가장 큰 값이 답이 될 것이라 생각했습니다.

예제랑 질문 게시판에 있는 케이스도 다 맞고, 직접 테케 몇 개 만들어서 해 보기도 했는데 다 생각한 대로 나왔습니다만, 어느 부분이 잘못되었는지 잘 모르겠습니다. 코드 보시고 도와주시면 감사하겠습니다.

좋은 하루 되세요 :)

#include <bits/stdc++.h>
using namespace std;

typedef struct {
    int y;
    int x;
} point;

point d[4] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};

int n, m;  // 세로, 가로
char ma[51][51];  // 맵 배열
bool visited[51][51];  // 방문 체크. BFS 돌릴 때마다 false로 초기화됨
int step_arr[51][51];  // 거리 저장할 배열. 얘도 매번 0으로 초기화됨
queue<point> q;

int bfs(int y, int x) {
    q.push({y, x});
    visited[y][x] = true;
    
    int maxstep = 0;
    while (!q.empty()) {
        point curr = q.front(); q.pop();
        int curr_y = curr.y, curr_x = curr.x;  // 현재 y, x 좌표
        for (auto it : d) {
            int dest_y = curr_y + it.y, dest_x = curr_x + it.x;  // 체크할 y, x 좌표
            if (dest_y >= 0 && dest_y < n && dest_x >= 0 && dest_x < m && ma[dest_y][dest_x] == 'L' && !visited[dest_y][dest_x]) {  // 경계 체크, 맵에서 L인지 체크, 방문 체크
                q.push({dest_y, dest_x});  
                visited[dest_y][dest_x] = true;
                step_arr[dest_y][dest_x] = step_arr[curr_y][curr_x] + 1;
                maxstep = max(step_arr[dest_y][dest_x], maxstep);
            }
        }
    }

    return maxstep;  // 그 섬에서 y, x에서 시작해서 가장 멀리 있는 L까지의 거리 리턴
}


int main() {
    int step, maxstep = 0;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf(" %1c", &ma[i][j]);
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (ma[i][j] == 'L') {
                memset(visited, false, 51 * 51);
                memset(step_arr, 0, 51 * 51);
                step = bfs(i, j);
                maxstep = max(maxstep, step);
            }
        }
    }
    
    printf("%d\n", maxstep);
    
    return 0;
}

dogdriip 5년 전 0

감사합니다 :>

memset 부분에서 세 번째 인자를 51 * 51 대신 sizeof(visited), sizeof(step_arr)로 각각 고쳐서 맞았습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2589 보물섬 도와주세요 (코드 주석 있음)

dogdriip 5년 전 0

dogdriip 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말