백준 - 17070 파이프 옮기기 1

문제

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

17070번: 파이프 옮기기 1

파이프를 맵의 마지막 위치로 옮길 수 있는 경우의 수를 구하는 문제였다.

 

문제 풀이

dfs로 완전탐색을 해서 풀 수 있었다.

처음 풀이 (고쳐서 맞추긴함)

문제를 풀다 시행착오가 2번 정도 있었다;

처음엔 문제를 제대로 읽지 않고 항상 3방향으로 갈 수 있는 상황이라 생각하고 풀어서 테케가 다 맞지 않았다.

 

그 다음에는 lx,ly,rx,ry를 넘겨 pipeDir를 구하고, 구한 pipeDir가 현재 pipe의 방향이라고 가정하고 풀었다. 나중에 안 사실이지만 현재 파이프 방향이 가로/세로 일 경우 세로/가로 로는 탐색하지 못하게 하는 부분에서 대각선이 아닐 경우에만 다음으로 넘어갈 수 있도록 했는데, 여기에 i!=2  대신 pipeDir!=2 를 사용해서 문제가 발생했었다. 그리고 백트래킹의 기초인 dfs가 끝나면 visit를 돌려놓는 것을 까먹어서;; 탐색을 덜하는 문제도 발생했다. 사실 이 문제는 무한 재귀를 돌 일이 없어서 (앞으로만 가니까) visit를 사용하지 않아도 됐다.ㅎ

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>

using namespace std;

int N;
int map[20][20];
int visit[3][20][20] = { 0 }; //방향, 좌표

//세로 가로 대각선
int dx[3] = { 1,0,1 };
int dy[3] = { 0,1,1 };

int answer = 0;

bool isInside(int x, int y) {
    if (x < N && y < N && x >= 0 && y >= 0) return true;
    return false;
}

bool isNotWall(int x, int y, int i) {
    if (i == 2) { // 대각선 방향, 3곳 체킹 필요
        // 위, 왼쪽
        if (map[x][y] == 0 && map[x - 1][y] == 0 && map[x][y - 1] == 0) return true;
    }
    else {
        if (map[x][y] == 0) return true;
    }
    return false;
}

int checkPipeDir(int lx, int ly, int rx, int ry) { //0: 가로 1: 세로 2: 대각선
    //세로: 0,0 1,0
    //가로 : 0,0, 0,1
    if (rx - lx == 0 && ry - ly == 1) return 0;
    else if (rx - lx == 1 && ry - ly == 0) return 1;
    else return 2;
}

void dfs(int lx, int ly, int rx, int ry) { //왼쪽끝, 오른쪽끝
    if (rx == N - 1 && ry == N - 1) {
        answer++;
        return;
    }
   
    //현재 파이프 놓여진 방향 확인 필요 - 가로/세로/대각선 
    int pipeDir = checkPipeDir(lx, ly, rx, ry);
    visit[pipeDir][rx][ry] = 1;

    for (int i = 0; i < 3; i++) {
        if (pipeDir == i && i != 2) continue;
        int nx = rx + dx[i];
        int ny = ry + dy[i];

        if (isInside(nx, ny) && isNotWall(nx, ny, i)) {
            dfs(rx, ry, nx, ny);
            visit[pipeDir][rx][ry] = 0;
        }
    }
}

int main(int argc, char** argv)
{
    scanf("%d", &N);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &map[i][j]);
        }
    }

    dfs(0, 0, 0, 1);

    printf("%d", answer);


    return 0;
}

 

 

두 번째 풀이

너무 복잡하게 풀어서 x,y,dir(현재 파이프 방향)만을 파라미터로 가지는 dfs를 다시 짰다. 그리고 dx와 dy의 순서도 가로/세로/대각선 으로 바꾸고 가로/세로 세로/가로 탐색 불가 체킹도 더 직관적으로 짰다.

 

휴,, 이렇게 맞추고 나니 처음 풀이의 문제점을 확실하게! 알게 돼서 처음 풀이도 조금 수정해서 정답이 나오게 했다.. 대체 왜 현재 방향을 보내면 될걸 lxlyrxry를 전부 보내고 pipeDir를 확인하게 했을까..? 알 수 없는 내 생각;

 

먼저 파이프가 가로, 세로, 대각선으로 놓여 있을 때 갈 수 있는 방향이 모두 달랐다. 세로/가로/대각선 방향의 3가지 dx/dy를 만들고 현재 파이프의 방향에 따라서 가로일 경우에는 세로로 못가고 세로일 경우에는 가로로 가지 못하게 막았다.

 

그리고 다음에 방문할 곳이 범위 안에 있고 파이프를 돌릴 때 벽이 나오지 않으면 탐색하도록 했다. 가로/세로 방향일 때에는 다음에 방문할 곳만 벽이 아니면 되고, 대각선 방향일 때에는 다음 방문할 곳의 왼쪽과 위까지 벽이 아니어야 방문할 수 있다. 

 

탐색하다가 x와 y가 (N-1, N-1)에 도달한다면 answer++ 하고 끝냈다.

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>

using namespace std;

int N;
int map[20][20];

//가로 세로 대각선
int dx[3] = { 0,1,1 };
int dy[3] = { 1,0,1 };

int answer = 0;

bool isInside(int x, int y) {
    if (x < N && y < N && x >= 0 && y >= 0) return true;
    return false;
}

bool isNotWall(int x, int y, int dir) {
    if (map[x][y] != 0) return false;

    if (dir == 2) { // 대각선 방향, 3곳 체킹 필요
        // 위, 왼쪽
        if (map[x - 1][y] != 0 || map[x][y - 1] != 0) return false;
    }

    return true;
}

void dfs(int x, int y, int dir) {
    if (x == N - 1 && y == N - 1) {
        answer++;
        return;
    }

    for (int i = 0; i < 3; i++) {
        if (dir == 0 && i == 1) continue;
        if (dir == 1 && i == 0) continue;

        int nx = x + dx[i];
        int ny = y + dy[i];

        if (isInside(nx, ny) && isNotWall(nx, ny, i)) {
            dfs(nx, ny, i);
        }
    }
}

int main(int argc, char** argv)
{
    scanf("%d", &N);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &map[i][j]);
        }
    }

    dfs(0, 1, 0);

    printf("%d", answer);


    return 0;
}