백준 알고리즘 17070 (파이프 옮기기 1) - C++

[문제] 백준 알고리즘 17070 (파이프 옮기기 1)

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

17070번: 파이프 옮기기 1

 

파이프를 오른쪽 또는 대각선 아래 또는 아래 방향으로 옮길 수 있다.

Map에서 1이 적힌 곳은 지날 수 없고, 45도 밖에 틀어지지 않는다.

대각선으로 갈 때는 파이프가 걸치는 모든 곳이 1이 아니어야한다.

 

진짜 처음으로 Python은 해결 못한 문제이다. (추가 시간 없음)

내 모든 지식을 동원해서, Pypy3로 해도 시간초과 문제는 해결되지 않는다.

BFS와 DFS를 활용해서 어떻게든 시간을 최대한 줄여보려고 시도했다.

계속 답은 나오는 것 같은데 시간 초과. 같은 방식으로 C++은 해결된다. 

Python으로는 동적계획법(DP)이나 분할정복 알고리즘으로 해결 가능해보인다.

(https://home-body.tistory.com/475 이 분 DP로 시간 초과 안나게 Python으로 해결하심)

[Algorithm][Python] 백준/BOJ - 17070_파이프 옮기기 1

 

[문제 해결]

1. BFS로 queue와 while을 활용한다.

2. 위치 정보와 가로(0)/세로(1)/대각선(2)을 표시하는 방향 정보를 queue에 저장한다.

3. queue의 앞에서 하나씩 불러오며 3가지의 방향을 진행한다.

4. 가로(0) -> 세로(1), 세로(1) -> 가로(0)는 갈 수 없으므로 합이 1일 때는 제외한다.

5. 대각선(2)일 때는 걸치는 부분이 모두 1이 아닌지를 체크한다.

6. 모두 만족하면 queue에 저장한다.

 

[C++]

#include <cstdio>
#include <cstring> // memeset
#include <queue>
using namespace std;

struct xyd {
	int x, y, dir;
};

queue<xyd> q;
int map[17][17];
int n, result = 0;;
int dx[3] = { 0, 1, 1 }; // row, col, cross
int dy[3] = { 1, 0, 1 }; // row, col, cross

int solve_bfs(int x, int y, int dir) {
	int cnt = 0;
	q.push({ x, y, dir });
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int dir = q.front().dir;
		q.pop();
		if (x == n - 1 && y == n - 1) {
			cnt++;
		}
		for (int i = 0; i < 3; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			int ndir = i;
			if ((ndir + dir) != 1) { // (row to col) or (col to row)
				if (nx < n && ny < n && !map[nx][ny]) {
					if (i == 2) { // cross
						if (!map[nx-1][ny] && !map[nx][ny-1]) {
							q.push({ nx, ny, ndir });
						}
					}
					else {
						q.push({ nx, ny, ndir });
					}
				}
			}
		}
	}
	return cnt;
}

int main() {
	memset(map, 0, sizeof(map));
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	result = solve_bfs(0, 1, 0);
	printf("%d", result);
	return 0;
}

 

[Python] (시간 초과)

from collections import deque
import sys
n = int(sys.stdin.readline())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dx = [0, 1, 1]  # 가로, 세로, 대각선
dy = [1, 0, 1]  # 가로, 세로, 대각선
q = deque()

def solve_bfs(x, y, dir):
    cnt = 0
    q.append((x, y, dir))
    while q:
        x, y, dir = q.popleft()
        if x == n-1 and y == n-1:
            cnt += 1
        for i in range(3):
            nx, ny, ndir = x + dx[i], y + dy[i], i
            if nx < n and ny < n and ndir + dir != 1:
                if not board[nx][ny]:
                    if i == 2:
                        if not board[nx-1][ny] and not board[nx][ny-1]:
                            q.append((nx, ny, ndir))
                    else:
                        q.append((nx, ny, ndir))
    return cnt

print(solve_bfs(0, 1, 0))