BOJ 2583,10026,7562... BFS/DFS

금요일부터 가볍게 BFS/DFS 기초 문제들을 풀어보았다. 

 

정답률이 높은 순으로 100026 적록색약, 2583 영역 구하기, 1926 그림, 7562 나이트의 이동 문제를 풀었는데 사실 큰 틀은 거의 똑같고, 문제에 따라 연결 요소, 연결 요소의 개수 등.. 의 차이가 있었을 뿐으로 거의 같은 문제들이었다.

 

2583번 영역 구하기의 경우 왼쪽 아래를 원점으로 카테시안 좌표계로 문제의 입력이 주어지는데, 배열에서 사용하는 좌표계의 그것과는 달라 머릿속에서 바로 떠오르지 않아 꽤나 곤욕스러웠다. 

 

7562번의 경우 위 문제들과 마찬가지로 BFS를 이용했는데, 최단거리 문제로 접근했다. BFS를 수행하며 도착하는 위치마다 이동에 필요한 횟수를 업데이트 하는 방법으로 문제를 해결했다.

 

#include <iostream>
#include <string.h>
#include <queue>

using namespace std;

struct P {int x,y,n;};
short dx[] = {1,1,2,2,-1,-1,-2,-2}, dy[] = {2,-2,1,-1,2,-2,1,-1};
int N;

int bfs(int x, int y, int d_x, int d_y, int visited[300][300]);
int main() {
    int visited[300][300];
    int K;
    scanf("%d",&K);
    for(int i=0;i<K;++i) {
        int x,y,d_x,d_y;
        scanf("%d",&N);
        for(int j=0;j<N;++j)
            for(int k=0;k<N;++k)
                visited[j][k] = INT32_MAX;
        scanf("%d%d%d%d",&x,&y,&d_x,&d_y);
        visited[y][x] = 0;

        cout << bfs(x,y,d_x,d_y,visited) << endl;
    }
}

int bound(P a) {return a.x>=0&&a.x<N&&a.y>=0&&a.y<N;}

int bfs(int x, int y, int d_x, int d_y, int visited[300][300]) {
    queue<P> Q;
    P a = {x,y,0};
    Q.push(a);
    visited[a.y][a.x] = a.n;
    while(!Q.empty()) {
        P tmp = Q.front();
        Q.pop();
        if(tmp.x == d_x && tmp.y == d_y) return tmp.n;
        for(int i=0;i<8;++i) {
            P nP = {tmp.x + dx[i],tmp.y + dy[i],tmp.n+1};
            if(bound(nP)&&visited[nP.y][nP.x]>tmp.n+1) {
                visited[nP.y][nP.x] = nP.n;
                Q.push(nP);
            }
        }

    }
}

#7562번 나이트의 이동 코드. (다른 문제들도 비슷한 구성을 취한다)

 

 

* 2178번 미로탐색 문제는 겨울 알고리즘 스터디때 푼 문제라 어떻게 풀었었나 궁금해 코드를 살펴보니.. 종점까지의 최단경로를 찾기 위해 입력 미로와 같은 크기의 배열을 선언하고, 방문하는 모든 위치들에 대한 거리를 저장하는 방법을 이용했었다. 지금 보니 7562번 문제 구현과 같은 방법으로 {x,y,거리} 구조체를 이용하면 일반적인 경우에서는 메모리도 절약할 수 있을 것이고, 배열 접근시 발생 할 수 있는 에러를 줄일 수 있었을것이다.