반응형
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 6987
- @P0
- softeer
- BOJ
- 소프티어
- 물채우기
- Docker
- dfs
- 성적평가
- Kafka
- compose
- incr
- 처우산정
- 이분탐색
- BFS
- 경력
- OFFSET
- 백준
- 오퍼레터
- 퇴사통보
- 백트래킹
- 매개변수탐색
- 처우협의
- 기술면접
- 13908
- msSQL
- upper_bound
- 연결요소
- 파라메트릭
- boj #19237 #어른 상어
Archives
- Today
- Total
기술 블로그
1938번 통나무 옮기기 본문
728x90
반응형
https://www.acmicpc.net/problem/1938
처음에 나의 접근은 방문처리를
3개(B,B,B)를 모두 하려 했지만, 생각해보니 굳이 이렇게 할 필요가 없었다.
즉, 중간만 방문처리 하면 된다.
또한, 가로, 세로 여부만 따지면 된다.
코드가 다소 긴 문제이다.
점 하나 하나 조건을 따져야하기 때문이다.
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 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 | #include <bits/stdc++.h> using namespace std; struct info { int y1, x1, y2, x2, y3, x3, direct; }; vector<vector<char> > v; pair<int, int> s[3], e[3]; queue<info> q; bool visit[55][55][2]; int N; int dy[4] = { -1, 1, 0, 0 }; int dx[4] = { 0, 0, -1, 1 }; void rotate(int y1, int x1, int y2, int x2, int y3, int x3, int i) { if (i == 0) // 가로에서 세로로 회전 { if (0 <= y1 - 1 && y1 + 1 < N && 0 <= y2 - 1 && y2 + 1 < N && 0 <= y3 - 1 && y3 + 1 < N) { if (v[y1 - 1][x1] != '1' && v[y1 + 1][x1] != '1' && v[y2 - 1][x2] != '1' && v[y2 + 1][x2] != '1' && v[y3 - 1][x3] != '1' && v[y3 + 1][x3] != '1' && !visit[y2][x2][1] ) { visit[y2][x2][1] = true; q.push({ y2 - 1, x2, y2, x2, y2 + 1, x2, 1 }); } } } else if (i == 1) // 세로에서 가로로 회전 { if (0 <= x1 - 1 && x1 + 1 < N && 0 <= x2 - 1 && x2 + 1 < N && 0 <= x3 - 1 && x3 + 1 < N) { if (v[y1][x1 - 1] != '1' && v[y1][x1 + 1] != '1' && v[y2][x2 - 1] != '1' && v[y2][x2 + 1] != '1' && v[y3][x3 - 1] != '1' && v[y3][x3 + 1] != '1' && !visit[y2][x2][0] ) { visit[y2][x2][0]; q.push({ y2, x2 - 1, y2, x2, y2, x2 + 1, 0 }); } } } } int bfs() { int ret = 0; if (s[0].first == s[1].first && s[1].first == s[2].first) { q.push({ s[0].first, s[0].second, s[1].first, s[1].second, s[2].first, s[2].second, 0 }); } else if (s[0].second == s[1].second && s[1].second == s[2].second) { q.push({ s[0].first, s[0].second, s[1].first, s[1].second, s[2].first, s[2].second, 1 }); } while (!q.empty()) { int qs = q.size(); while (qs--) { int r1 = q.front().y1; int c1 = q.front().x1; int r2 = q.front().y2; int c2 = q.front().x2; int r3 = q.front().y3; int c3 = q.front().x3; int direct = q.front().direct; q.pop(); if (r1 == e[0].first && c1 == e[0].second && r2 == e[1].first && c2 == e[1].second && r3 == e[2].first && c3 == e[2].second) { return ret; } rotate(r1, c1, r2, c2, r3, c3, direct); for (int i = 0; i < 4; i++) { int y1 = r1 + dy[i]; int x1 = c1 + dx[i]; int y2 = r2 + dy[i]; int x2 = c2 + dx[i]; int y3 = r3 + dy[i]; int x3 = c3 + dx[i]; if (y1 < 0 || y1 >= N || x1 < 0 || x1 >= N || y2 < 0 || y2 >= N || x2 < 0 || x2 >= N || y3 < 0 || y3 >= N || x3 < 0 || x3 >= N || v[y1][x1] == '1' || v[y2][x2] == '1' || v[y3][x3] == '1' || visit[y2][x2][direct] ) continue; visit[y2][x2][direct] = true; q.push({ y1, x1, y2, x2, y3, x3, direct }); } } ++ret; } return 0; } int main(void) { int idx1 = 0, idx2 = 0; char c; cin >> N; for (int i = 0; i < N; i++) { vector<char> input; for (int j = 0; j < N; j++) { cin >> c; if (c == 'B') s[idx1++] = { i, j }; else if (c == 'E') e[idx2++] = { i, j }; input.push_back(c); } v.push_back(input); } printf("%d\n", bfs()); return 0; } | cs |
728x90
반응형
'알고리즘 문제 > BOJ' 카테고리의 다른 글
2606번 바이러스 (0) | 2019.09.22 |
---|---|
17471번 게리맨더링 (0) | 2019.09.21 |
1152번 단어의 개수 (0) | 2019.09.15 |
2230번 수 고르기 (0) | 2019.09.15 |
1049번 기타줄 (0) | 2019.09.14 |