[백준]파이프 옮기기1

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

17070번: 파이프 옮기기 1

 

DFS/BFS로 풀었을 경우인데 DFS가 시간이랑 메모리 면에서 효율적이었다..

간단한 그래프 문제였다 bfs,dfs모두 해결가능할거 같다. 방향이 3가지로 정해져있고 하나 착각했던것은 대각선으로 

갈때 상좌 모두 비어있어야 된다는 것이었고 쉬운 문제였던거 같다.

전의 놓아진 상태를 알아야 뒤에 놓아질 경우를 정하기때문에 구조체를 활용했다.

<BFS>

#include <iostream>
#include <queue>
using namespace std;
 
struct path {
    int r, c, dir;
};
 
int dr[] = { 0,1,1 }, dc[] = { 1,1,0 }; //오른0 오른대각선아래1 아래2
int map[17][17];
int N, cnt = 0;
queue<path>q1;
 
void bfs() {
    while (!q1.empty()) {
        int nr = q1.front().r, nc = q1.front().c, dir = q1.front().dir;
        q1.pop();
        if (nr == N && nc == N)cnt++;
 
        for (int i = 0; i < 3; i++) {
            //놓을 수 없는 경우들 pass
            if (dir == 0) { if (i == 2) continue; }
            else if (dir == 2) { if (i == 0) continue; }
 
            int r = nr + dr[i], c = nc + dc[i];
 
            if (i == 0 || i == 2) {
                if (map[r][c] == 1 || r<1 || c<1 || r>N || c>N) continue;
            }
            else if (i == 1) {
                if (r > N || c > N || map[r][c] == 1 || map[r - 1][c] == 1 || map[r][c - 1] == 1) continue;
            }
            q1.push({ r,c,i });
        }
    }
}
 
int main()
{    
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
        }
    }
    q1.push({ 1,2,0 }); //시작점
    bfs();
    printf("%d\n", cnt);
    return 0;
}

 

<DFS>

#include <iostream>
using namespace std;
 
int dr[] = { 0,1,1 }, dc[] = { 1,1,0 }; //오른0 오른대각선아래1 아래2
int map[17][17];
int N, cnt = 0;
 
void dfs(int r, int c, int dir) {
    if (r == N && c == N) {
        cnt++;
        return;
    }
 
    for (int i = 0; i < 3; i++) {
        if (dir == 0) { if (i == 2) continue; }
        else if (dir == 2) { if (i == 0) continue; }
 
        int nr = r + dr[i], nc = c + dc[i];
 
        if (i == 0 || i == 2) {
            if (map[nr][nc] == 1 || nr<1 || nc<1 || nr>N || nc>N) continue;
        }
        else if (i == 1) {
            if (nr > N || nc > N || map[nr][nc] == 1 || map[nr - 1][nc] == 1 || map[nr][nc - 1] == 1) continue;
        }
 
        dfs(nr, nc, i);
    }
}
 
int main()
{    
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
        }
    }
    dfs(1, 2, 0); //시작점
    printf("%d\n", cnt);
    return 0;
}