JUST WRITE IT. HomeArchivesTagsCategories
백준 1938번 통나무 옮기기
|AlgorithmBOJ|

#1938. 통나무 옮기기

Problem

Solution

  1. 통나무 중점 좌표를 토대로 BFS 탐색을 하였다.
    중심을 기준으로 그대로(회전), 상, 하, 좌, 우로 이동하면 각각 작동횟수 + 1이기에
    BFS로 탐색하는게 최적이다.
    중복 탐색을 막기 위해 3차원 방문 배열을 두어 중점 좌표의 각 모양(타입)에 따라 표시를 하였다.
  2. 중점 좌표로 이동하다보니 이동 후 다음을 꼭 확인해야 한다.
    1. 평지 범위를 벗어나지 않는지
      세 좌표 모두 범위를 벗어나지 않도록 확인해야한다.
    2. 방문한 지점인지
    3. 움직일 수 있는지
      상하좌우 → 움직인 세 좌표에 ‘1’이 없는지 확인
      회전 → 움직인 중점좌표 기준으로 3x3dp ‘1’이 없는지 확인
  3. 도착 지점에 도착하면 종료

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
#include <vector>
#include <queue>
#define endl "\n"
#define MAX 50
using namespace std;
int N, ans = 1e9;
char land[MAX + 1][MAX + 1];
bool visited[MAX + 1][MAX + 1][2];
vector<pair<int, int>> start_point;
vector<pair<int, int>> end_point;
int dr[5] = { 0, -1, 1, 0, 0 };
int dc[5] = { 0, 0, 0, -1, 1 };
struct Log {
	int type; // 0 : 가로, 1 : 세로
	int r, c; // 중점 좌표
};
bool isIn(int r, int c, int type) { // 통나무가 평지 범위인지
	if (type == 0) c--;
	else r--;
	for (int i = 0; i < 3; ++i) {
		if (r < 0 || c < 0 || r > N - 1 || c > N - 1) return false;
		if (type == 0) c++;
		else r++;
	}
	return true;
}
bool isEnd(int r, int c, int type) { // EEE에 도착했는지
	if (type == 0) c--;
	else r--;
	for (int i = 0; i < end_point.size(); i++)
	{
		if (end_point[i].first != r || end_point[i].second != c) return false;
		if (type == 0) c++;
		else r++;
	}
	return true;
}
bool Check(int r, int c, int type) { // 이동이 가능한지
	if (type == 0) c--;
	else r--;
	for (int i = 0; i < 3; ++i) {
		if (land[r][c] == '1') return false;
		if (type == 0) c++;
		else r++;
	}
	return true;
}
bool CheckRotate(int r, int c, int type) { // 회전이 가능한지
	int sr = r - 1, sc = c - 1;
	for (int i = sr; i < sr + 3; ++i) {
		for (int j = sc; j < sc+ 3; ++j) {
			if (land[i][j] == '1') return false;
		}
	}
	return true;
}
void BFS() {
	queue<Log> q;   
	int type, r, c;
	if (start_point[0].first == start_point[1].first) {
		type = 0; r = start_point[0].first; c = start_point[1].second;
	}
	else {
		type = 1; c = start_point[0].second; r = start_point[1].first;
	}
	q.push({ type, r, c });
	visited[r][c][type] = true;
	int cnt = 0;
	while (int s = q.size()) {
		while (s--) {
			int r = q.front().r, c = q.front().c;
			int type = q.front().type;
			if (isEnd(r, c, type)) {
				ans = cnt;
				return;
			}
			q.pop();
			for (int dir = 0; dir < 5; ++dir) {
				if (dir == 0 || dir == 1) type = (type+1) % 2; // 회전 후 타입 원래대로
				int nr = r + dr[dir];
				int nc = c + dc[dir];
				if (!isIn(nr, nc, type)) continue;
				if (visited[nr][nc][type]) continue;
				if (dir == 0) if (!CheckRotate(nr, nc, type)) continue; // 3 x 3 확인 후 회전
				if (Check(nr, nc, type)) {
					visited[nr][nc][type] = true;
					q.push({ type, nr, nc });
				}
			}
		}
		cnt++;
	}
}

int main() {
	cin >> N;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> land[i][j];
			if (land[i][j] == 'B') start_point.push_back({ i, j });
			else if (land[i][j] == 'E') end_point.push_back({ i, j });
		}
	}
	BFS();
	if (ans == 1e9) ans = 0;
	cout << ans < endl;
	return 0;
}
Algorithm