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

삼성 A형 기출 문제인 17070번

17070번: 파이프 옮기기 1

이렇게 BFS로 풀어서 제출했는데 시간초과가 났다.

n = int(input())
from sys import stdin
li = []
for i in range(n):
    li.append(list(map(int, stdin.readline().split())))
import collections
q = collections.deque()
q.append(((0, 0), (0, 1)))
count = 0
while q:
    cur = q.popleft()
    if cur[1] == (n - 1, n - 1):
        count += 1
    if cur[0][0] == cur[1][0]:
        if cur[1][1] + 1 < n and li[cur[1][0]][cur[1][1] + 1] == 0:
            q.append((cur[1], (cur[1][0], cur[1][1] + 1)))
        if cur[1][1] + 1 < n and cur[1][0] + 1 < n and li[cur[1][0]][cur[1][1] + 1] == 0 and li[cur[1][0] + 1][cur[1][1]] == 0 and  li[cur[1][0] + 1][cur[1][1] + 1] == 0:
            q.append((cur[1], (cur[1][0] + 1, cur[1][1] + 1)))
    elif cur[0][1] == cur[1][1]:
        if cur[1][0] + 1 < n and li[cur[1][0] + 1][cur[1][1]] == 0:
            q.append((cur[1], (cur[1][0] + 1, cur[1][1])))
        if cur[1][1] + 1 < n and cur[1][0] + 1 < n and li[cur[1][0]][cur[1][1] + 1] == 0 and li[cur[1][0] + 1][cur[1][1]] == 0 and  li[cur[1][0] + 1][cur[1][1] + 1] == 0:
            q.append((cur[1], (cur[1][0] + 1, cur[1][1] + 1)))
    else:
        if cur[1][1] + 1 < n and li[cur[1][0]][cur[1][1] + 1] == 0:
            q.append((cur[1], (cur[1][0], cur[1][1] + 1)))
        if cur[1][0] + 1 < n and li[cur[1][0] + 1][cur[1][1]] == 0:
            q.append((cur[1], (cur[1][0] + 1, cur[1][1])))
        if cur[1][1] + 1 < n and cur[1][0] + 1 < n and li[cur[1][0]][cur[1][1] + 1] == 0 and li[cur[1][0] + 1][cur[1][1]] == 0 and  li[cur[1][0] + 1][cur[1][1] + 1] == 0:
            q.append((cur[1], (cur[1][0] + 1, cur[1][1] + 1)))
print(count)

찾아보니까 이 방법으로 풀려면 파이썬이 아닌 다른 언어로 풀어야 한다고 한다.

파이썬으로 풀어서 맞으신 분들은 다 동적계획법으로 푸신 분들만 맞았다고 한다.

역시 알고리즘 풀 때 쓰는 언어를 C++로 바꿔야 하는 걸까

가장 오래 배운 언어가 C++(2018년 3월에 처음 접함)이고 그 다음이 Java(2018년 9월에 처음 접함), 그리고 파이썬(2019년 9월에 처음 접함)이 가장 최근에 배운건데

요즘에 안 써서 그런지 C++은 어색해지고 오히려 배운지 6개월도 안 된 언어인 파이썬이 가장 편해졌다.

파이썬이 문자열 다루기도 좋고 다른 부분에서도 정말 편한데 고민이다.

 

다음 날 2020.01.19

위의 코드를 그대로 C++로 바꿔서 성공

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<vector> li(n, vector(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> li[i][j];
		}
	}
	queue<pair<pair<int, int>, pair<int, int>>> q;
	q.push(make_pair(make_pair(0, 0), make_pair(0, 1)));
	int count = 0;
	while (!q.empty()) {
		int row1 = q.front().first.first;
		int col1 = q.front().first.second;
		int row2 = q.front().second.first;
		int col2 = q.front().second.second;
		q.pop();
		if (row2 == n - 1 && col2 == n - 1) {
			count++;
			continue;
		}
		if (row1 == row2) {
			if (col2 + 1 < n && li[row2][col2 + 1] == 0)
				q.push(make_pair(make_pair(row2, col2), make_pair(row2, col2 + 1)));
			if (col2 + 1 < n && row2 + 1 < n && li[row2][col2 + 1] == 0 && li[row2 + 1][col2] == 0 && li[row2 + 1][col2 + 1] == 0)
				q.push(make_pair(make_pair(row2, col2), make_pair(row2 + 1, col2 + 1)));
		}
		else if (col1 == col2) {
			if (row2 + 1 < n && li[row2 + 1][col2] == 0)
				q.push(make_pair(make_pair(row2, col2), make_pair(row2 + 1, col2)));
			if (col2 + 1 < n && row2 + 1 < n && li[row2][col2 + 1] == 0 && li[row2 + 1][col2] == 0 && li[row2 + 1][col2 + 1] == 0)
				q.push(make_pair(make_pair(row2, col2), make_pair(row2 + 1, col2 + 1)));
		}
		else {
			if (col2 + 1 < n && li[row2][col2 + 1] == 0)
				q.push(make_pair(make_pair(row2, col2), make_pair(row2, col2 + 1)));
			if (row2 + 1 < n && li[row2 + 1][col2] == 0)
				q.push(make_pair(make_pair(row2, col2), make_pair(row2 + 1, col2)));
			if (col2 + 1 < n && row2 + 1 < n && li[row2][col2 + 1] == 0 && li[row2 + 1][col2] == 0 && li[row2 + 1][col2 + 1] == 0)
				q.push(make_pair(make_pair(row2, col2), make_pair(row2 + 1, col2 + 1)));
		}
	}
	cout << count << endl;
	return 0;
}

역시 C/C++이 속도 면에서는 확실히 우수하다.

<tuple>이라는 라이브러리의 pair과 make_pair() 함수 꼭 기억해야겠다.

이걸 이용하니 클래스나 구조체를 따로 만들지 않아도 돼서 편하다.