글 읽기 - 문제를 제가 제대로 이해한 건지 알고 싶습니다.

lsask59 3년 전 0

다음 코드로 예제 입력을 돌려 봤을 때 예제 입력 4, 5의 경우 둘 다 1이 나옵니다. 그런데 웃긴 건 프로그램을 돌린 것이 아닌 직접 그려서 알아본 인구 이동 수, 즉 연합 수도 둘 다 1인데 연합 수=인구 이동 수가 아닌가요?

#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

#define VVI vector<vector<int> >
#define VISITED 0
#define NONVISITED 1
#define NOUNION 2

struct Node {
    int r;
    int c;
};

vector<vector<vector<Node> > > edge;
VVI visited; // 해당 노드 방문 시 true

vector<Node> nonVisited(VVI vis)
{
    vector<Node> result;

    result.clear();

    for (int i = 0; i < vis.size(); i++) {
        for (int j = 0; j < vis[i].size(); j++) {
            if (vis[i][j] == NONVISITED) {
                result.push_back({i, j});
            }
        }
    }

    return result;
}

void bfs(Node cur)
{
    queue<Node> q; // 방문하지 않은 노드 발견 시 큐에 넣음
    Node here, there; // 현재 노드, 현재 노드와 연결되어 있는 노드

    // 시작 노드
    visited[cur.r][cur.c] = VISITED; // 해당 노드 방문 했으므로 true
    q.push(cur); // 방문하지 않았던 노드이므로 큐에 넣음

    while (!q.empty()) { // 큐가 빌 때 까지 수행
        here = q.front(); // 큐의 맨 앞에 있는 노드 확인
        q.pop(); // 큐의 맨 앞에 있는 원소 제거

        for (int i = 0; i < edge[here.r][here.c].size(); i++) { // 현재 노드와 연결되어 있는 모든 노드 확인
            there = edge[here.r][here.c][i];

            if (visited[there.r][there.c] == VISITED) continue; // 이미 방문했던 노드인 경우 출력할 필요 없으니 넘어감
            visited[there.r][there.c] = VISITED; // 방문하지 않았던 노드인 경우 이제 방문 했으므로 true
            q.push(there); // 이 노드 큐에 넣음 (위에서 값 출력하는데 이용)
        }
    }
}

int main()
{
    int N, L, R;
    int i, j;
    VVI A;
    int diff; // 국경 공유하는 두 나라의 인구 수 차이
    vector<Node> nonVisit; // BFS 돌린 후 방문하지 않은 노트 확인
    int count = 0;

    scanf("%d %d %d", &N, &L, &R);

    A.resize(N);
    edge.resize(N);
    visited.resize(N);

    for (i = 0; i < N; i++) {
        A[i].resize(N);
        edge[i].resize(N);
        visited[i].resize(N);

        for (j = 0; j < N; j++) {
            scanf("%d", &A[i][j]);
            visited[i][j] = NOUNION;
        }
    }

    // 세로 방향 국경선 확인
    for (i = 0; i < N; i++) {
        for (j = 0; j < N - 1; j++) {
            diff = abs(A[i][j+1] - A[i][j]);

            if (diff >= L && diff <= R) {
                edge[i][j].push_back({i, j+1});
                edge[i][j+1].push_back({i, j});
                visited[i][j] = NONVISITED;
                visited[i][j+1] = NONVISITED;
            }
        }
    }

    // 가로 방향 국경선 확인
    for (i = 0; i < N - 1; i++) {
        for (j = 0; j < N; j++) {
            diff = abs(A[i][j] - A[i+1][j]);

            if (diff >= L && diff <= R) {
                edge[i][j].push_back({i+1, j});
                edge[i+1][j].push_back({i, j});
                visited[i][j] = NONVISITED;
                visited[i+1][j] = NONVISITED;
            }
        }
    }

    i = j = 0;

    while (1) {
        if (visited[i][j] == NOUNION) {
            if (j == N - 1) {
                j = 0;
                i++;
            }
            else j++;
            
            continue;
        }

        bfs({i, j});
        count++;

        nonVisit = nonVisited(visited);

        if (nonVisit.size() == 0) {
            break;
        }
        else {
            i = nonVisit[0].r;
            j = nonVisit[0].c;
        }
    }

    printf("%d", count);

    return 0;
}

rlagusdnr120 2년 전 0

저도 문제 풀다보니까 이동한 연합의 총 개수가아니라, 연합이 이동을 한 날짜의 총 합이더라고요,,

첫날에 2연합이 이동하고, 둘째날에 3연합이 이동해도 답은 2가 나와야하더라고요

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

문제

문제

출처

ICPC

문제를 제가 제대로 이해한 건지 알고 싶습니다.

lsask59 3년 전 0

rlagusdnr120 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말