글 읽기 - 미로탐색 문제(bfs)

dladbwls8 8년 전 0

예제로는 올바르게 나오나 제출하니 틀렸다고 합니다ㅠ 이전에 dfs/bfs 문제에서도 풀리지 않으니 뭔가 bfs를 이용하는 방법이 잘못된게 아닌가 스스로 생각도 해봅니다. 혹시 제가 놓친 부분이 없는지 알려주세요.

#include <stdio.h>
#include <queue>
using namespace std;
 
/*2015년 10월 8일
 넓이 우선 탐색(bfs)을 통해 푼 도착점까지의 최단거리를 찾는 미로찾기 문제*/
struct POINT { int a; int b; };
int h = 0;  // 세로(행)
int w = 0;  // 가로(열)
 
char maze[100][100];    // 미로
int visited[100][100];  // BFS를 통해 저장한 각 점에서 최단 경로의 길이
 
int sa = 0, sb = 0;
int ga = 0, gb = 0;
 
POINT around[4] = { {1,0},{-1.0},{0,1},{0,-1} };
void input() {
    scanf("%d", &h);
    scanf("%d", &w);
     
    for (int i = 0; i < h; i++) {
            scanf("%s", maze[i]);
    }
 
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            maze[i][j] -= 48;
            //printf("%d", maze[i][j]);
        }
        //printf("\n");
    }
}
bool safe(int x, int y) {
    // 미로 배열의 내부에 있는지 검사한다.
    if (x >= 0 && x < h&&y >= 0 && y < w)
        return true;
    else
        return false;
}
void solve() {
    queue<POINT> q;
    POINT cur;
    sa = 0;
    sb = 0;
    ga = h - 1;
    gb = w - 1;
    q.push({ sa,sb });
    visited[sa][sb] = 1;                    // 시작지점에서의 경로 0
    visited[ga][gb] = -1;               
 
    while (!q.empty()) {                    // 큐가 빌 때 까지
        cur = q.front(); q.pop();
        if (cur.a == ga && cur.b == gb)     // 도착점에 도달하면
        {
            break;
        }
        for (int i = 0; i < 4; i++) {        // 현재 지점에서 동서남북 탐색(bfs)
            int x = cur.a + around[i].a;    // 탐색 지점 x (row)
            int y = cur.b + around[i].b;    // 탐색 지점 y (col)
         
            // 방문하지 않았고, 길이며, 미로의 경계를 벗어나지 않았다면,
            if (visited[x][y] <= 0 && maze[x][y] == 1&&safe(x, y)) {                 
                q.push({ x,y });                            // 큐에 삽입한다.
                visited[x][y] = visited[cur.a][cur.b] + 1;  // 방문한 지점까지의 경로의 길이
            }       
        }
    }
}
void output() {
 
    //for (int i = 0; i < h; i++) {
    //  for (int j = 0; j < w; j++) {
    //      printf("%d", visited[i][j]);
    //  }
    //  printf("\n");
    //}
    printf("%d", visited[ga][gb]);
}
int main() {
    input();
    solve();
    output();
}

kbu1564 8년 전 0

safe 함수에서 왜 조건 비교가

x 좌표값이 h 높이와 대소 비교하고

y 좌표값이 w 너비와 대소 비교를 하는지요?

바뀌어야 하는게 아닐까요?

dladbwls8 8년 전 0

헷갈리게 해서 죄송합니다. x가 x좌표 뜻이아니라 행으로 쓰였습니다ㅎㅎ 그래서 행의 길이를 뜻하는 h가 경계조건이 된거구요

yukariko 8년 전 3

String으로 입력받기때문에 배열크기가 부족합니다.

dladbwls8 8년 전 0

정말 감사합니다ㅠㅠㅠ 배열의 크기를 바꿨더니 바로 성공하네요!!! 문자열 끝도 입력받아야한다는 것을 잊었습니다^_^

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

문제

문제

출처

ICPC

미로탐색 문제(bfs)

dladbwls8 8년 전 0

kbu1564 8년 전 0

dladbwls8 8년 전 0

yukariko 8년 전 3

dladbwls8 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말