백준(boj) 17070_파이프 옮기기1 (파이썬, c++)

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

풀이

---

가로 방향일 때 (x, y+1), (x+1, y+1) 부분에 벽이 없으면 갈 수 있고,

세로 방향은 (x+1, y), (x+1, y+1) 부분에 벽이 없으면 갈 수 있고,

대각선 방향은 (x+1, y), (x, y+1), (x+1, y+1) 부분에 벽이 없으면 갈 수 있다.

대각선 방향으로 갈 때는 옆,아래,대각선 모두 벽이 없어야 갈 수 있으므로 따로 처리해 주었다.

(n-1, n-1)로 가는 모든 경우의 수를 구하는 문제이다. BFS를 사용하였다.

python3

#c++은 통과, python은 시간초과남 dp로 다시 풀기
from sys import*
from collections import*
input = lambda:stdin.readline().strip()
​
def checkD(dx, dy):
    if dx:
        if dy: return 2
        else: return 1
    else:
        return 0               #세가지 경우밖에 없음, dx==0이면 dy=1임
dd=[[(0,1), (1,1)],           #옆 방향
    [(1,0), (1,1)],             #아래
    [(0,1), (1,0), (1,1)]]      #대각선
n=int(input())
a=[list(map(int,input().split()))for _ in range(n)]
q=deque()
q.append((0,1,0))   #x, y, d
cnt = 0
while q:
    x, y, d = q.popleft()
    if x==n-1 and y==n-1:
        cnt+=1
    for dx, dy in dd[d]:
        nx, ny, nd = x+dx, y+dy, checkD(dx, dy)
        if nx<0 or ny<0 or nx>n-1 or ny>n-1 or a[nx][ny]: continue
        if nd==2:
            if a[x][ny] or a[nx][y]: continue
        q.append((nx, ny, nd))
print(cnt)

C++

#include<cstdio>
#include<queue>
#include<tuple>
#include<iostream>
using namespace std;
typedef tuple<int, int, int> T;
int checkD(int dx, int dy){
    if(dx){
        if(dy) return 2;
        else return 1;
    }
    else return 0;
}
​
int dd[3][3][2]={{{0, 1}, {1, 1}},
                {{1, 0}, {1, 1}},
                {{0, 1}, {1, 0}, {1, 1}}};
​
int main()
{
    int n;
    int a[20][20];
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%d", &a[i][j]);
        }
    }
    queue<T> q;
    q.push(make_tuple(0,1,0));
    int cnt=0;
    while(!q.empty()){
        int x, y, d;
        tie(x, y, d) = q.front();
        q.pop();
        if(x==n-1 && y==n-1)cnt++;
        for(auto k : dd[d]){
            int dx, dy, nx, ny, nd;
            dx = k[0], dy = k[1];
            if(dx==0 && dy==0)continue;
            nx = x+dx; ny = y+dy; nd = checkD(dx, dy);
            if(nx<0 || ny<0 || nx>n-1 || ny>n-1 || a[nx][ny]) continue;
            if(nd==2){
                if(a[x][ny] || a[nx][y]) continue;
            }
            q.push(make_tuple(nx, ny, nd));
        }
    }
    printf("%d",cnt);
    return 0;
}

고찰

---

1.파이썬이 느리단걸 다시 일깨워준 문제.. c++도 바로바로 사용 가능하게끔 열심히 공부해야 겠다.