글 읽기 - 2589번 문제 질문입니다.

vel1024 3년 전 0

2589번 보물섬 문제를 풀면서 BFS 로 풀려고 아래와 같이 C++ 코드를 짰습니다.

문제에서 제시한 예제 입력 / 출력의 경우에는 제대로 나오긴 하는데,

어떤 점에서 틀린답이 되는지 알려주시면 감사하겠습니다.

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#define MAX 51

using namespace std;

int initX, initY, maxValue; 
string adj[MAX];            
int checked[MAX][MAX];      
int dx[4] = {0, 0, -1, 1};  
int dy[4] = {1, -1, 0, 0};  
int sum[MAX][MAX];        

void BFS(int i, int j)
{
    queue<pair<int, int>> pos; 
    checked[i][j] = true;
    pos.push({i, j});
    sum[i][j]++;

    while (!pos.empty())
    {
        int x = pos.front().first;
        int y = pos.front().second;
        pos.pop();

        for (int k = 0; k < 4; k++)
        {
            int newX = x + dx[k];
            int newY = y + dy[k];
            if ((0 <= newX && newX < initX) && (0 <= newY && newY < initY))
            {
                if (adj[newX][newY] == 'L' && !checked[newX][newY])
                {
                    checked[newX][newY] = true;
                    pos.push({newX, newY});
                    sum[newX][newY] = sum[x][y] + 1;
                    maxValue = max(maxValue, sum[newX][newY]);
                }
            }
        }
    }
}

int main()
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> initX >> initY;

    for (int i = 0; i < initX; i++)
    {
        cin >> adj[i];
    }

    for (int i = 0; i < initX; i++)
    {
        for (int j = 0; j < initY; j++)
        {
            if (adj[i][j] == 'L' && !checked[i][j])
            {
                BFS(i, j);
            }
        }
    }

    printf("%d", maxValue);
    return 0;
}

whdgurclzls 3년 전 0

sum배열 초기화가 안되어 있습니다.

vel1024 3년 전 0

죄송합니다만 sum 배열 초기화 했음에도 틀렸다고 나옵니다..

whdgurclzls 3년 전 0

63번째줄 check배열 확인하는게 문제가 되어 보입니다.

앞에서 탐색된 L이 시작점으로 오고, 다른곳과의 최단거리로 있을시 문제가 됩니다.

매 방문시 초기화 시켜주셔야 합니다.

whdgurclzls 3년 전 0

위에 설명이 모호해서..

어떤 L이든 정답이 될 가능성이 있습니다. 모든 L을 방문하며 최단거리를 구해가며 그 중에서 가장 작은 값을 출력해야합니다.

vel1024 3년 전 0

나중에 다시 보니 이해가 됬습니다 감사합니다.

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

문제

문제

출처

ICPC

2589번 문제 질문입니다.

vel1024 3년 전 0

whdgurclzls 3년 전 0

vel1024 3년 전 0

whdgurclzls 3년 전 0

whdgurclzls 3년 전 0

vel1024 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말