글 읽기 - 100%.. 간절하게 반례 부탁드립니다 ㅠㅠㅠ

huh0918 2년 전 0

심지어 100프로까지 갔는데 틀렸습니다..

map에는 ground, group을 나눠서 땅의 특징을 기록했습니다.

ground는 0이면 바다, 1이면 육지입니다.

group은, 섬을 나눈겁니다. 섬이 세개면 각각 1,2,3으로 기록되었습니다.(기록은 dfs이용해서 함)

그리고 바다가아닌 육지 전체다 큐에 넣고 bfs를 돌려서

d(distance)를 갱신해가며 최솟값을 찾았습니다.

bfs 방식은,

자기자신과 그룹이 다르고, 그룹이 0이다(아직 다른 그룹에게 안먹혔다)면 그 땅을 자기 그룹에 편입시키고 d를 업데이트해나갔습니다.

그러다가, 인접한 땅이 이미 다른그룹의 땅이면 그제서야 최소 거리로 만나게 되는거죠.

어디가 틀렸을까요.. 도와주시면 정말 감사하겠습니다!!

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Point
{
    int x, y;
    Point(int _x=0, int _y=0): x(_x), y(_y) {}
};
struct Area
{
    int ground, group;
    Area(int grd=0, int grp=0): ground(grd), group(grp) {}
    void Print() // 디버깅용
    {
        cout << "( " << ground <<", "
        << group << ") ";
    }
};

int n;
int dx[] ={0,0,1,-1};
int dy[] ={1,-1,0,0};
queue<Point> q;
Area map[101][101];
int d[101][101];

void dfs(const Point p, int group)
{
    q.push(Point(p.x,p.y));
    //섬들을 순회할 역할이기때문에, 순회하는 김에 
    // 섬들을 전부 큐에 넣는다.
    map[p.x][p.y].group = group;
    
    for (int i=0; i <4; i++){
        int nx = p.x + dx[i];
        int ny = p.y + dy[i];
        if (nx <1 || nx>n || ny<1 || ny>n)
            continue;
            
        if (map[nx][ny].ground ==1 && map[nx][ny].group==0){
            dfs(Point(nx, ny), group);
        }
        
    }
    
    
    
}

int main()
{
    cin >> n;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            cin >> map[i][j].ground;
        }
    }
    
    
    int group =1;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(map[i][j].ground ==1 && map[i][j].group==0 )
            {
                dfs(Point(i,j), group++);
            }
        }
    }
    
    
    while( !q.empty() )
    {
        Point p = q.front(); q.pop();
        int grp, grd;
        grp = map[p.x][p.y].group;
        grd = map[p.x][p.y].ground;
        
        for (int i=0; i<4; i++)
        {
            int nx = p.x+dx[i];
            int ny = p.y+dy[i];
            if (nx <1 || nx>n || ny<1 || ny>n)
                continue;
            // 이미 자기땅이면 패스
            if (  map[nx][ny].group == grp  )
                continue;
                
                
             // 다른 그룹이 안먹은 바다라면..  
            if(map[nx][ny].group == 0)
            {
                d[nx][ny]=d[p.x][p.y]+1;
                map[nx][ny].group = grp;
                q.push(Point(nx, ny));
            }
            // 다른그룹 만나면 끝.
            else
            {
                cout << d[p.x][p.y] + d[nx][ny] << endl;
                return 0;
            }
        }
        
   
    } // bfs while    
}

yhj1937 2년 전 6

1 0 0 0 1

0 0 0 0 0

0 1 0 0 1

huh0918 2년 전 0

통찰력이 대단하십니다..

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

문제

문제

출처

ICPC

100%.. 간절하게 반례 부탁드립니다 ㅠㅠㅠ

huh0918 2년 전 0

yhj1937 2년 전 6

huh0918 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말