-
https://www.acmicpc.net/problem/2234
2234번: 성곽
문제 대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오. 이 성에 있는 방의 개수 가장 넓은 방의 넓이 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기 위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을
www.acmicpc.net
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518#include<iostream>#include<queue>#include<vector>#include<algorithm>using namespace std;struct PAIR {int x, y;PAIR(int x, int y) {this->x = x;this->y = y;}};int w, h;int map[55][55];int dist[55][55];bool d[55][55];bool dos[55][55];vector<PAIR> v;int dx[] = { 0,-1,0,1 };int dy[] = { -1,0,1,0 };int bfs(int x, int y, int c) {queue<PAIR> q;q.push(PAIR(x, y));d[x][y] = true;dist[x][y] = c;int cnt = 0;while (!q.empty()) {x = q.front().x; y = q.front().y;dist[x][y] = c;cnt++;q.pop();for (int i = 0; i < 4; i++) {int nx = x + dx[i]; int ny = y + dy[i];if (nx >= 0 && nx < h && ny >= 0 && ny < w &&d[nx][ny] == false) {if (map[x][y] == 1) {if (i != 0) {d[nx][ny] = true;q.push(PAIR(nx, ny));}else {continue;}}else if (map[x][y] == 2) {if (i != 1) {d[nx][ny] = true;q.push(PAIR(nx, ny));}else {continue;}}else if (map[x][y] == 4) {if (i != 2) {d[nx][ny] = true;q.push(PAIR(nx, ny));}else {continue;}}else if (map[x][y] == 8) {if (i != 3) {d[nx][ny] = true;q.push(PAIR(nx, ny));}else {continue;}}else if (map[x][y] == 3) {if (i != 0 && i != 1) {d[nx][ny] = true;q.push(PAIR(nx, ny));}else {continue;}}else if (map[x][y] == 5) {if (i != 0 && i != 2) {d[nx][ny] = true;q.push(PAIR(nx, ny));}else {continue;}}else if (map[x][y] == 9) {if (i != 0 && i != 3) {d[nx][ny] = true;q.push(PAIR(nx, ny));}else {continue;}}else if (map[x][y] == 6) {if (i == 0 || i == 3) {d[nx][ny] = true;q.push(PAIR(nx, ny));}else {continue;}}else if (map[x][y] == 15) {continue;}else if (map[x][y] == 10) {if (i != 1 && i != 3) {d[nx][ny] = true;q.push(PAIR(nx, ny));}else {continue;}}else if (map[x][y] == 7) {if (i != 0 && i != 1 && i != 2) {d[nx][ny] = true;q.push(PAIR(nx, ny));}else {continue;}}else if (map[x][y] == 11) {if (i != 0 && i != 1 && i != 3) {d[nx][ny] = true;q.push(PAIR(nx, ny));}else {continue;}}else if (map[x][y] == 12) {if (i != 2 && i != 3) {d[nx][ny] = true;q.push(PAIR(nx, ny));}else {continue;}}else if (map[x][y] == 13) {if (i != 0 && i != 2 && i != 3) {d[nx][ny] = true;q.push(PAIR(nx, ny));}else {continue;}}else if (map[x][y] == 0) {d[nx][ny] = true;q.push(PAIR(nx, ny));}else if (map[x][y] == 14) {if (i != 1 && i != 2 && i != 3) {d[nx][ny] = true;q.push(PAIR(nx, ny));}else {continue;}}}}}return cnt;}void bfs2(int x, int y) {queue<PAIR> q;q.push(PAIR(x, y));dos[x][y] = true;int cnt = 0;while (!q.empty()) {x = q.front().x; y = q.front().y;cnt++;q.pop();for (int i = 0; i < 4; i++) {int nx = x + dx[i]; int ny = y + dy[i];if (nx >= 0 && nx < h && ny >= 0 && ny < w && dos[nx][ny] == false) {if (map[x][y] == 1) {if (i != 0) {dos[nx][ny] = true;q.push(PAIR(nx, ny));}else {if (dist[nx][ny] != dist[x][y]) {bool ins = false;for (int i = 0; i < v.size(); i++) {if (v[i].x == dist[x][y] && v[i].y == dist[nx][ny]) {ins = true;break;}}if (!ins)v.push_back(PAIR(dist[x][y], dist[nx][ny]));}}}else if (map[x][y] == 2) {if (i != 1) {dos[nx][ny] = true;q.push(PAIR(nx, ny));}else {if (dist[nx][ny] != dist[x][y]) {bool ins = false;for (int i = 0; i < v.size(); i++) {if (v[i].x == dist[x][y] && v[i].y == dist[nx][ny]) {ins = true; break;}}if (!ins)v.push_back(PAIR(dist[x][y], dist[nx][ny]));}}}else if (map[x][y] == 4) {if (i != 2) {dos[nx][ny] = true;q.push(PAIR(nx, ny));}else {if (dist[nx][ny] != dist[x][y]) {bool ins = false;for (int i = 0; i < v.size(); i++) {if (v[i].x == dist[x][y] && v[i].y == dist[nx][ny]) {ins = true; break;}}if (!ins)v.push_back(PAIR(dist[x][y], dist[nx][ny]));}}}else if (map[x][y] == 8) {if (i != 3) {dos[nx][ny] = true;q.push(PAIR(nx, ny));}else {if (dist[nx][ny] != dist[x][y]) {bool ins = false;for (int i = 0; i < v.size(); i++) {if (v[i].x == dist[x][y] && v[i].y == dist[nx][ny]) {ins = true; break;}}if (!ins)v.push_back(PAIR(dist[x][y], dist[nx][ny]));}}}else if (map[x][y] == 3) {if (i != 0 && i != 1) {dos[nx][ny] = true;q.push(PAIR(nx, ny));}else {if (dist[nx][ny] != dist[x][y]) {bool ins = false;for (int i = 0; i < v.size(); i++) {if (v[i].x == dist[x][y] && v[i].y == dist[nx][ny]) {ins = true; break;}}if (!ins)v.push_back(PAIR(dist[x][y], dist[nx][ny]));}}}else if (map[x][y] == 5) {if (i != 0 && i != 2) {dos[nx][ny] = true;q.push(PAIR(nx, ny));}else {if (dist[nx][ny] != dist[x][y]) {bool ins = false;for (int i = 0; i < v.size(); i++) {if (v[i].x == dist[x][y] && v[i].y == dist[nx][ny]) {ins = true; break;}}if (!ins)v.push_back(PAIR(dist[x][y], dist[nx][ny]));}}}else if (map[x][y] == 9) {if (i != 0 && i != 3) {dos[nx][ny] = true;q.push(PAIR(nx, ny));}else {if (dist[nx][ny] != dist[x][y]) {bool ins = false;for (int i = 0; i < v.size(); i++) {if (v[i].x == dist[x][y] && v[i].y == dist[nx][ny]) {ins = true; break;}}if (!ins)v.push_back(PAIR(dist[x][y], dist[nx][ny]));}}}else if (map[x][y] == 6) {if (i == 0 || i == 3) {dos[nx][ny] = true;q.push(PAIR(nx, ny));}else {if (dist[nx][ny] != dist[x][y]) {bool ins = false;for (int i = 0; i < v.size(); i++) {if (v[i].x == dist[x][y] && v[i].y == dist[nx][ny]) {ins = true; break;}}if (!ins)v.push_back(PAIR(dist[x][y], dist[nx][ny]));}}}else if (map[x][y] == 10) {if (i != 1 && i != 3) {dos[nx][ny] = true;q.push(PAIR(nx, ny));}else {if (dist[nx][ny] != dist[x][y]) {bool ins = false;for (int i = 0; i < v.size(); i++) {if (v[i].x == dist[x][y] && v[i].y == dist[nx][ny]) {ins = true; break;}}if (!ins)v.push_back(PAIR(dist[x][y], dist[nx][ny]));}}}else if (map[x][y] == 7) {if (i != 0 && i != 1 && i != 2) {dos[nx][ny] = true;q.push(PAIR(nx, ny));}else {if (dist[nx][ny] != dist[x][y]) {bool ins = false;for (int i = 0; i < v.size(); i++) {if (v[i].x == dist[x][y] && v[i].y == dist[nx][ny]) {ins = true; break;}}if (!ins)v.push_back(PAIR(dist[x][y], dist[nx][ny]));}}}else if (map[x][y] == 11) {if (i != 0 && i != 1 && i != 3) {dos[nx][ny] = true;q.push(PAIR(nx, ny));}else {if (dist[nx][ny] != dist[x][y]) {bool ins = false;for (int i = 0; i < v.size(); i++) {if (v[i].x == dist[x][y] && v[i].y == dist[nx][ny]) {ins = true; break;}}if (!ins)v.push_back(PAIR(dist[x][y], dist[nx][ny]));}}}else if (map[x][y] == 12) {if (i != 2 && i != 3) {dos[nx][ny] = true;q.push(PAIR(nx, ny));}else {if (dist[nx][ny] != dist[x][y]) {bool ins = false;for (int i = 0; i < v.size(); i++) {if (v[i].x == dist[x][y] && v[i].y == dist[nx][ny]) {ins = true; break;}}if (!ins)v.push_back(PAIR(dist[x][y], dist[nx][ny]));}}}else if (map[x][y] == 13) {if (i != 0 && i != 2 && i != 3) {dos[nx][ny] = true;q.push(PAIR(nx, ny));}else {if (dist[nx][ny] != dist[x][y]) {bool ins = false;for (int i = 0; i < v.size(); i++) {if (v[i].x == dist[x][y] && v[i].y == dist[nx][ny]) {ins = true; break;}}if (!ins)v.push_back(PAIR(dist[x][y], dist[nx][ny]));}}}else if (map[x][y] == 0) {dos[nx][ny] = true;q.push(PAIR(nx, ny));}if (dist[nx][ny] != dist[x][y]) {bool ins = false;for (int i = 0; i < v.size(); i++) {if (v[i].x == dist[x][y] && v[i].y == dist[nx][ny]) {ins = true; break;}}if (!ins)v.push_back(PAIR(dist[x][y], dist[nx][ny]));}else if (map[x][y] == 14) {if (i != 1 && i != 2 && i != 3) {dos[nx][ny] = true;q.push(PAIR(nx, ny));}else {if (dist[nx][ny] != dist[x][y]) {bool ins = false;for (int i = 0; i < v.size(); i++) {if (v[i].x == dist[x][y] && v[i].y == dist[nx][ny]) {ins = true; break;}}if(!ins)v.push_back(PAIR(dist[x][y], dist[nx][ny]));}}}else {if (dist[nx][ny] != dist[x][y]) {bool ins = false;for (int i = 0; i < v.size(); i++) {if (v[i].x == dist[x][y] && v[i].y == dist[nx][ny]) {ins = true; break;}}if (!ins)v.push_back(PAIR(dist[x][y], dist[nx][ny]));}}}}}}int main() {ios_base::sync_with_stdio(0);cin.tie(0);cin >> w >> h;for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {cin >> map[i][j];}}int room = 0;int maxe = 0;int c = 1;vector<int> score;for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {if (d[i][j] == false) {room++;int b = bfs(i, j,c);score.push_back((b));c++;if (maxe < b) maxe = b;}}}for (int i = 0; i < h; i++) {for (int j = 0; j < c; j++) {if (dos[i][j] == false) {bfs2(i, j);}}}cout << room << '\n';cout << maxe << '\n';int maxx = 0;for (int i = 0; i < v.size(); i++) {if (maxx < score[v[i].x - 1] + score[v[i].y - 1]) {maxx = score[v[i].x - 1] + score[v[i].y - 1];}}cout << maxx << '\n';}http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter성곽문제다
BFS를 두번해서 풀었고, 첫번쨰 BFS는 두번쨰까지의 답안을 구하기위해서 진행하고, 마지막 BFS는 인접한 영역의 넓이를 알기위해 벡터를선언하고 이웃하는 곳을 벡터에담아서 최대 넓이를 계산하는방식으로 진행했다
일단 코드가 공포스럽게 긴데, 그냥 1,2,4,8,9,10.... 생각해보면-> 2로 나눈나머지나 나누는것을 통해 충분히계산할수있는데
사실 거기까지생각하기는 조금 실전에서 힘들지않을까 하는생각이들었고
그냥 전부다 해보는방법을 선택했던것같다.