[PS]맞왜틀 시리즈3 정렬범위

알고리즘 문제를 풀다보면 아무리 코드를 봐도 맞는데 틀린다.

우리는 그럴때 이렇게 말한다.

우선 아래 코드를 보자

int main() {
/*
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1, 000), 간선의 개수 M(1 ≤ M ≤ 10, 000), 탐색을 시작할 정점의 번호 V가 주어진다.
다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다.
어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다.
입력으로 주어지는 간선은 양방향이다.
*/
    scanf("%d%d%d", &N, &M, &V);
    for (int i = 0; i < M; i++) {
        int s, e;
        scanf("%d%d", &s, &e);
        edge[s].push_back(e);
        edge[e].push_back(s);
    }
    for (int i = 0; i < N; i++) {
        sort(edge[i].begin(), edge[i].end(), cmp);
    }
    //-----------------Solution----------------
 
    return 0;
}

해당 코드는 백준 1260 dfs bfs 문제이다. 문제는 아래 링크를 참조하자

라인 4번부터 보면 입력에 대한 설명이 있다.

간선(edge)정보는 임의로 들어오기 때문에 먼저 vector로 전부 받은후 정렬시키도록 코드를 구현하였다.

이후 DFS BFS를 수행한다.

 

맞왜틀 포인트는 16번째 for 반복문의 범위이다.

N의 범위가 1≤N≤1,000 이기 때문에 반복자 i의 범위도 1≤i≤N 가 되도록 해야하는데

처음 작성한 위 코드는 범위가 0≤i<N으로 되어있다.

 

위와같이 범위설정을 한 경우 예제입력은 통과하지만 문제를 제출하면 틀리게 된다.

정점N에 연결된 간선은 정렬이 되지 않아 탐색 조건을 위배하기 때문이다.

전체 코드는 밑에 있으니 참조하자

 

 

문제 주소

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

전체 코드

//https://www.acmicpc.net/problem/1260
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
/*
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.
단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고,
더 이상 방문할 수 있는 점이 없는 경우 종료한다.
정점 번호는 1번부터 N번까지이다.
*/
 
 
int N, M, V;
vector<int> edge[1001];
int visiteddfs[1001];
int visitedbfs[1001];
queue<int> dfsRet, bfsRet;
vector<int> v;
queue<int> q;
 
void start_bfs() {
    q.push(V);
    visitedbfs[V] = 1;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        bfsRet.push(cur);
        for (int i = 0; i < edge[cur].size(); i++) {
            if (visitedbfs[edge[cur][i]] == 0) {
                visitedbfs[edge[cur][i]] = 1;
                q.push(edge[cur][i]);
            }
        }
    }
}
void dfs(){
    //dfs
    int cur = v.back();
    dfsRet.push(cur);
    for (int i = 0; i < edge[cur].size(); i++) {
        int next = edge[cur][i];
        if (visiteddfs[next] == 0) {
            v.push_back(next);
            visiteddfs[next] = 1;
            dfs();
        }
    }
    v.pop_back();
    //dfsEnd
}
void start_dfs() {
 
    v.push_back(V);
    visiteddfs[V] = 1;
    dfs();
}
bool cmp(int a, int b) {
    return a < b;
}
int main() {
/*
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1, 000), 간선의 개수 M(1 ≤ M ≤ 10, 000), 탐색을 시작할 정점의 번호 V가 주어진다.
다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다.
어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다.
입력으로 주어지는 간선은 양방향이다.
*/
    scanf("%d%d%d", &N, &M, &V);
    for (int i = 0; i < M; i++) {
        int s, e;
        scanf("%d%d", &s, &e);
        edge[s].push_back(e);
        edge[e].push_back(s);
    }
    for (int i = 1; i <= N; i++) {
        sort(edge[i].begin(), edge[i].end(), cmp);
    }
    //-----------------Solution----------------
    start_dfs();
    start_bfs();
    /*
    출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다.V부터 방문된 점을 순서대로 출력하면 된다.
*/
    while (!dfsRet.empty()) {
        printf("%d ", dfsRet.front());
        dfsRet.pop();
    }
    printf("\n");
    
    while (!bfsRet.empty()) {
        printf("%d ", bfsRet.front());
        bfsRet.pop();
    }
    
    return 0;
}