글 읽기 - 왜틀렸을까요?

200924460 7년 전 0

dfs가 보다 bfs가 좋다고하여

bfs로 짰는데 예제는 맞으나 결과는 틀렷다고 하네요.

#include <stdio.h>
#include <iostream>

using namespace std; 
 
int n,m, cnt; 
int map[105][105]; 
int x[105], y[105], l[105]; 
 

void enqueue(int _x, int _y, int _l)
{
    x[cnt] = _x;
    y[cnt] = _y;
    l[cnt] = _l;
    cnt++;
}
 
void BFS(int _x, int _y)
{
    int pos = 0; 
    enqueue(_x, _y, 1);
    while (pos < cnt && (x[pos] != n - 1 || y[pos] != m - 1))
    {
        map[x[pos]][y[pos]] = 0;
 

        if (y[pos] > 0 && map[x[pos]][y[pos] - 1] == 1)
            enqueue(x[pos], y[pos] - 1, l[pos] + 1);
        if (y[pos] < m - 1 && map[x[pos]][y[pos] + 1] == 1)
            enqueue(x[pos], y[pos] + 1, l[pos] + 1);
        if (x[pos] > 0 && map[x[pos] - 1][y[pos]] == 1)
            enqueue(x[pos] - 1, y[pos], l[pos] + 1);
        if (x[pos] < n - 1 && map[x[pos] + 1][y[pos]] == 1)
            enqueue(x[pos] + 1, y[pos], l[pos] + 1);
        pos++;
    }

    if (pos < cnt)
        printf("%d\n", l[pos]);
}
 
int main()
{
    int i, j;
   cin>>n>>m;
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++)
            scanf("%1d", &map[i][j]);
    BFS(0, 0); 
    return 0;
}

plzrun 7년 전 0

죄송합니다. 틀린것 같다고 처음에 지적했는데, 코드를 보니까 제가 지적한 부분은 틀리지 않았네요.

다시 보니까 check배열이 없어서 그런것 같습니다. 방문한곳을 다시 방문하지 않도록 체크배열 만들어줬더니 통과했습니다.

#include <stdio.h>
#include <iostream>

using namespace std; 

int n,m, cnt; 
int map[105][105]; 
int x[105], y[105], l[105]; 
bool chk[105][105];


void enqueue(int _x, int _y, int _l)
{
    x[cnt] = _x;
    y[cnt] = _y;
    l[cnt] = _l;
    cnt++;
}

void BFS(int _x, int _y)
{
    int pos = 0;
    enqueue(_x, _y, 1);
    chk[_x][_y]=true;
    while (pos < cnt && (x[pos] != n - 1 || y[pos] != m - 1))
    {
        map[x[pos]][y[pos]] = 0;
        int a=x[pos], b=y[pos];

        if (y[pos] > 0 && map[x[pos]][y[pos] - 1] == 1 && !chk[a][b-1]) {
            chk[a][b-1]=true;
            enqueue(x[pos], y[pos] - 1, l[pos] + 1);
        }
        if (y[pos] < m - 1 && map[x[pos]][y[pos] + 1] == 1 && !chk[a][b+1]) {
            chk[a][b+1]=true;
            enqueue(x[pos], y[pos] + 1, l[pos] + 1);
        }
        if (x[pos] > 0 && map[x[pos] - 1][y[pos]] == 1 && !chk[a-1][b]) {
            chk[a-1][b]=true;
            enqueue(x[pos] - 1, y[pos], l[pos] + 1);
        }
        if (x[pos] < n - 1 && map[x[pos] + 1][y[pos]] == 1 && !chk[a+1][b]) {
            chk[a+1][b]=true;
            enqueue(x[pos] + 1, y[pos], l[pos] + 1);
        }
        pos++;
    }

    if (pos < cnt)
        printf("%d\n", l[pos]);
}

int main()
{
    int i, j;
    cin>>n>>m;
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++)
            scanf("%1d", &map[i][j]);
    BFS(0, 0);
    return 0;
}

plzrun 7년 전 1

위의 댓글 작성자인데...

그래도 코드는 아래와 같은 코드로 전향하시는 것을 추천드립니다. :)

그래프 문제는 코드가 다 정형화 되어있으니까요...

참고로 bfs와 dfs를 구현하실때에는

bfs는 방문하기전에 반드시 체크를 해야하고

dfs는 방문하고 나서 체크를 해야 합니다.

이 점만 주의하셔서 코딩하시면 될 것 같아요.

#include <cstdio>
#include <queue>
using namespace std;
int v[101][101],dx[]={0,0,1,-1},dy[]={1,-1,0,0};
bool chk[101][101];
queue<pair<int,int> > q;
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            scanf("%1d",&v[i][j]);
        }
    }
    int ans=1;
    chk[0][0]=true;
    q.push(make_pair(0,0));
    while(!q.empty()) {
        int sz=q.size();
        for(int z=0; z<sz; z++) {
            int x=q.front().first, y=q.front().second; q.pop();
            if(x==n-1&&y==m-1) {
                printf("%d", ans);
                return 0;
            }
            for(int i=0; i<4; i++) {
                int nx=x+dx[i], ny=y+dy[i];
                if(nx<0||ny<0||nx>=n||ny>=m) continue;
                if(chk[nx][ny] || !v[nx][ny]) continue;
                chk[nx][ny]=true;
                q.push(make_pair(nx,ny));
            }
        }
        ans++;
    }
    return 0;
}

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

문제

문제

출처

ICPC

왜틀렸을까요?

200924460 7년 전 0

plzrun 7년 전 0

plzrun 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말