[백준 17070번] 파이프 옮기기 1

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

17070번: 파이프 옮기기 1

풀이) 

너무 간단한 문제였다. 방향을 1 - 가로 2 - 대각선 3 - 세로 놓고, 갈 수 있는지 확인을 하고 완전탐색(dfs)를 진행하면 해결되는 문제였다.  

#include <iostream>
using namespace std;

int map[17][17];
int N, cnt = 0;

void dfs(int x, int y, int dir)
{
    if (x == N && y == N)
    {
        cnt++;
        return;
    }
    
    if (dir == 1)
    {
        if (!map[x][y + 1] && y + 1 <= N)
            dfs(x, y + 1, 1);
        if (!map[x + 1][y + 1] && !map[x][y + 1] && !map[x + 1][y] && x + 1 <= N && y + 1 <= N)
            dfs(x + 1, y + 1, 2);
    }
    else if (dir == 2)
    {
        if (!map[x][y + 1] && y + 1 <= N)
            dfs(x, y + 1, 1);
        if (!map[x + 1][y] && x + 1 <= N)
            dfs(x + 1, y, 3);
        if (!map[x + 1][y + 1] && !map[x][y + 1] && !map[x + 1][y] && x + 1 <= N && y + 1 <= N)
            dfs(x + 1, y + 1, 2);
    }
    else if (dir == 3)
    {
        if (!map[x + 1][y] && x + 1 <= N)
            dfs(x + 1, y, 3);
        if (!map[x + 1][y + 1] && !map[x][y + 1] && !map[x + 1][y] && x + 1 <= N && y + 1 <= N)
            dfs(x + 1, y + 1, 2);
    }
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N;

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
			cin >> map[i][j];
    dfs(1, 2, 1);
	cout << cnt;
    return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!