글 읽기 - 안녕하세요! 68프로에서 실패하여, 한번 봐주시면 감사하겠습니다. (주석 있음)

taxol1203 3년 전 0

우선 반례를 다 대입해봐도 맞고, 혹시 사이즈 문제일까봐 배열 크기를 [100][100]으로 넉넉하게 잡아도 틀려 범위 문제는 아닌것 같습니다.

분명히 제가 놓친 반례가 있는데 찾기가 어렵네요.

사실 어떻게 하면 찾아가며 생각하는지도 잘 모르겠습니다 ㅠ. 고수님들 있으시면 불쌍한 양을 도와주시면 감사하겠습니다

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

//코드 정리 방법 : Ctrl + A 후, Ctrl + K,F

/*
2589번 - 보물섬
[출처](https://www.acmicpc.net/problem/2589)

접근 방법:
1. 땅이라고 인식되는 좌표를 저장합니다
2. 저장한 좌표를 하나씩 꺼내가며 BFS 함수의 인자로 넣어, 모든 땅을 검사합니다.
3. 매개변수로 받은 좌표에서 시작해, 갈 수 있는 최단 거리를 구합니다.
4. biggest()을 통해 그 최단거리 중 가장 가장 긴 시간이 걸리는 육지 두곳의 거리를 구합니다.
5. init()을 통해 앞선 BFS()에서 사용한 visited와 road를 초기화 하고 다음 좌표를 받아 앞선 3,4번 과정을 반복합니다.
구현:

*/

int n, m, result;
char graph[50][50];             //초기 지도
bool visited[50][50];           //방문 여부를 확인하기 위한 배열
int road[50][50];               //최단 거리를 저장하기 위한 배열
queue<pair<int, int>> land;     //땅 좌표만 모아놓은 queue

int goy[4] = { -1, 1, 0, 0 };
int gox[4] = { 0, 0, -1, 1 };

void BFS(int y, int x);
void biggest();
void init();
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    char temp;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> graph[i][j];
            if (graph[i][j] == 'L') {
                land.push(make_pair(i, j));         //땅으로 인식 된 좌표는 저장합니다.
            }
        }
    }
    while (!land.empty()) {             //앞서 저장한 땅 좌표를 모두 탐색합니다.
        int y = land.front().first;
        int x = land.front().second;
        land.pop();
        BFS(y, x);                      
        biggest();                  //구한 최단 거리 중 가장 큰 값을 저장합니다.
        init();                     
    }
    cout << result;

    return 0;
}
void BFS(int y, int x) {
    queue<pair<int, int>> curL;
    curL.push(make_pair(y, x));
    int cury, curx;
    while (!curL.empty()) {
        y = curL.front().first;
        x = curL.front().second;
        curL.pop();
        for (int i = 0; i < 4; i++) {       //한 좌표의 상,하,좌,우 를 탐색합니다.
            cury = y + goy[i];
            curx = x + gox[i];
            if (!visited[cury][curx] && -1 < cury && cury < n && -1 < curx && curx < m && graph[cury][curx] == 'L') {           //방문하지 않았고, 좌표가 땅(L)이며, 그래프 범위를 넘어가지 않는 경우
                visited[cury][curx] = true;                 //방문했다고 표기합니다.
                road[cury][curx] = road[y][x] + 1;          //시작 점에서 한칸 이동한 값을 저장합니다.
                curL.push(make_pair(cury, curx));
            }
        }
    }
}
void biggest() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (road[i][j] != 0) {
                result = max(result, road[i][j]);
            }
        }
    }
}
void init() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            road[i][j] = 0;
            visited[i][j] = false;
        }
    }
}

kms9937 3년 전 3

맨처음 시작점에 방문체크를 해주시면 맞았습니다가 나옵니다.

즉 52번째 줄 아래에 visited[y][x]=true를 추가해주시면 됩니다.

taxol1203 3년 전 0

아하! 첫 시작점을 제가 체크를 빠트렸군요 ㅠㅠㅠ 감사합니다 고수님!

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

문제

문제

출처

ICPC

안녕하세요! 68프로에서 실패하여, 한번 봐주시면 감사하겠습니다. (주석 있음)

taxol1203 3년 전 0

kms9937 3년 전 3

taxol1203 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말