반응형
알고리즘 분류 : BFS
B 지점에 있는 통나무를 E 지점에 옮겨야 하는 문제다. 통나무의 길이는 3으로 고정되어 있고, 상하좌우 이동과 회전 이동이 가능하다. 길이가 3이라는 점과, 회전이 가능하다는 점이 굉장히 귀찮은 문제다. 특별한 아이디어가 안 떠올라서 다소 무식하게 코딩했다.
- 통나무의 길이는 3으로 고정되므로, 가운데 정점을 이동 좌표로 삼는다.
- 방문 체크와 이동 거리를 저장할 배열 dist를 3차원으로 선언한다. 인덱스는 [x 좌표] [y 좌표] [회전 방향] 이다.
- 회전 방향은 가로일 때 0, 세로일 때 1이다.
- 문제에 주어진 조건처럼, 이동할 때 다른 나무(1)이 없어야 한다.
- 나무의 회전 방향에 따라 이동 가능한지 체크를 다르게 한다.
C++ 소스코드
#include <cstdio> #include <cstring> #include <vector> #include <queue> using namespace std; struct tree { int x, y, z; }; int n, m; char a[50][50]; int dist[50][50][2]; queue<tree> q; const int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1}, dy[] = {0, 0, -1, 1, -1, 1, -1, 1}; bool out(int x, int y) { return x < 0 || x >= n || y < 0 || y >= n; } bool check(int x, int y) { if (out(x, y) || a[x][y] == '1') return false; return true; } void one(int x, int y, int z, int dx, int dy) { if (!out(x+dx, y+dy) && a[x+dx][y+dy] != '1' && dist[x][y][z] == -1) { q.push({x, y, z}); dist[x][y][z] = dist[x-dx][y-dy][z]+1; } } void three(int x, int y, int z, int nx, int ny, int dx, int dy) { if (!out(nx, ny) && dist[nx][ny][z] == -1) { if (a[nx][ny] != '1' && a[nx-dx][ny-dy] != '1' && a[nx+dx][ny+dy] != '1') { q.push({nx, ny, z}); dist[nx][ny][z] = dist[x][y][z]+1; } } } void rotate(int x, int y, int z) { for (int i=0; i<8; i++) { int nx = x+dx[i], ny = y+dy[i]; if (!check(nx, ny)) return; } if (dist[x][y][!z] == -1) { q.push({x, y, !z}); dist[x][y][!z] = dist[x][y][z]+1; } } void bfs() { while (!q.empty()) { int x = q.front().x, y = q.front().y, z = q.front().z; q.pop(); int mx = 0, my = 0; if (z) mx = 1; else my = 1; if (a[x][y] == 'E' && a[x-mx][y-my] == 'E' && a[x+mx][y+my] == 'E') { printf("%d\n", dist[x][y][z]); return; } if (z) { one(x-1, y, z, -1, 0); one(x+1, y, z, 1, 0); three(x, y, z, x, y+1, 1, 0); three(x, y, z, x, y-1, 1, 0); rotate(x, y, z); } else { one(x, y-1, z, 0, -1); one(x, y+1, z, 0, 1); three(x, y, z, x+1, y, 0, 1); three(x, y, z, x-1, y, 0, 1); rotate(x, y, z); } } printf("0\n"); } int main() { scanf("%d", &n); memset(dist, -1, sizeof(dist)); vector<tree> v; for (int i=0; i<n; i++) { for (int j=0; j<n; j++) { scanf(" %1c", &a[i][j]); if (a[i][j] == 'B') v.push_back({i, j}); } } int x = v[1].x, y = v[1].y, z = v[0].x != v[1].x; q.push({x, y, z}); dist[x][y][z] = 0; bfs(); return 0; }
Python 3 소스코드
from collections import deque from sys import stdin input = stdin.readline def out(x, y): return x < 0 or x >= n or y < 0 or y >= n def check(x, y): if out(x, y) or a[x][y] == '1': return False else: return True def one(x, y, z, dx, dy): if not out(x+dx, y+dy) and a[x+dx][y+dy] != '1' and dist[x][y][z] == -1: q.append((x, y, z)) dist[x][y][z] = dist[x-dx][y-dy][z]+1 def three(x, y, z, nx, ny, dx, dy): if not out(nx, ny) and dist[nx][ny][z] == -1: if a[nx][ny] != '1' and a[nx-dx][ny-dy] != '1' and a[nx+dx][ny+dy] != '1': q.append((nx, ny, z)) dist[nx][ny][z] = dist[x][y][z]+1 def rotate(x, y, z): for dx, dy in (-1,0), (1,0), (0,-1), (0,1), (-1,-1), (-1,1), (1,-1), (1, 1): nx, ny = x+dx, y+dy if not check(nx, ny): return if dist[x][y][not z] == -1: q.append((x, y, not z)) dist[x][y][not z] = dist[x][y][z]+1 def bfs(): while q: x, y, z = q.popleft() mx, my = 0, 0 if z: mx = 1 else: my = 1 if a[x][y] == 'E' and a[x-mx][y-my] == 'E' and a[x+mx][y+my] == 'E': print(dist[x][y][z]) return if z: one(x-1, y, z, -1, 0) one(x+1, y, z, 1, 0) three(x, y, z, x, y+1, 1, 0) three(x, y, z, x, y-1, 1, 0) rotate(x, y, z) else: one(x, y-1, z, 0, -1) one(x, y+1, z, 0, 1) three(x, y, z, x+1, y, 0, 1) three(x, y, z, x-1, y, 0, 1) rotate(x, y, z) print(0) n = int(input()) a = [list(input().strip()) for _ in range(n)] v = [] for i in range(n): for j in range(n): if a[i][j] == 'B': v.append((i, j)) x, y = v[1] _x, _y = v[0] z = _x != x q = deque() dist = [[[-1, -1] for _ in range(n)] for _ in range(n)] q.append((x, y, z)) dist[x][y][z] = 0 bfs()
참고
- 백준 온라인 저지 : BOJ 1938
반응형