1109 섬

1109 섬 https://www.acmicpc.net/problem/1109

섬들은 'x'로, 물은 '.'로 표시된 지도가 주어진다.
섬은 가로,세로,대각선이 연결되있으면 같은 섬이고 물은 가로,세로만 연결할 수 있다.
어떤 섬 A가 포함하고 있는 가장 높이가 높은섬의 높이가 K라면 A의 높이는 K+1이다.
높이가 0인섬부터 가장높은 섬의 높이까지 차례대로 개수를 구하는 문제이다.

한달전쯤 시도했다가 실패한 문제였다.
예전에 BFS를 약 한달동안 판적이 있어서 자신있었는데 
이 문제를 접하고나니 아직 갈길이 멀다고 생각이 든다.

우선 바깥쪽 섬에서 안쪽 섬으로 들어오는 형식으로 풀어야지만 풀 수 있다.

처음에는 지도의 윤곽에 존재하는 물에서 시작을 해야한다.
문제예시처럼 지도의 모든 윤곽이 섬에의해 둘러싸여있다면 물을 queue에 넣을 수 없다.
이러한 경우에는 따로 예외처리를 해주었다.
물을 queue에 넣고 BFS를 진행하다가 섬을 만나면 물의 근원지 섬(?)에서 만난 섬을 연결시켜 주었다.
이렇게 연결된 인접리스트가 구성되면 DFS로 원하는 답을 한번에 구했다.

#include <cstdio> #include <cstring> #include <vector> #include <queue> #include <algorithm> using namespace std; int N, M; char map[51][51]; int visit[51][51]; bool adjmat[2555][2555]; vector<int> adj[2555]; queue<int> isl, wat; int cnt = 1; int dy[] = { -1,0,0,1,1,1,-1,-1 }; int dx[] = { 0,1,-1,0,-1,1,1,-1 }; vector<int> pos[2555]; vector<int> curr; bool chk[2555]; void island(int iy, int ix) {     visit[iy][ix] = cnt;     isl.push(iy*M + ix);     pos[cnt].push_back(iy*M + ix);     while (!isl.empty()) {         int y = isl.front() / M, x = isl.front() % M;         isl.pop();           for (int i = 0;i < 8;i++) {             int ny = y + dy[i], nx = x + dx[i];             if (ny < 0 || ny >= N || nx < 0 || nx >= M || visit[ny][nx] != 0 || map[ny][nx] == '.') continue;             visit[ny][nx] = cnt;             isl.push(ny*M + nx);             pos[cnt].push_back(ny*M + nx);         }     } } void water(int iy, int ix, int here) {     if (visit[iy][ix] != 0) return;     visit[iy][ix] = -1;     wat.push(iy*M + ix);     while (!wat.empty()) {         int y = wat.front() / M, x = wat.front() % M;         wat.pop();           for (int i = 0;i < 4;i++) {             int ny = y + dy[i], nx = x + dx[i];             if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;             if (map[ny][nx] == '.' && visit[ny][nx] == 0) {                 visit[ny][nx] = -1;                 wat.push(ny*M + nx);             }             else if (map[ny][nx] == 'x') {                 if (!adjmat[here][visit[ny][nx]]) {                     adjmat[here][visit[ny][nx]] = true;                     adj[here].push_back(visit[ny][nx]);                     curr.push_back(visit[ny][nx]);                 //    printf("%d->%d\n", here, visit[ny][nx]);                 }             }         }     } } void solve(int num) {     queue<int> q;     for (int n = 0;n < pos[num].size();n++) q.push(pos[num][n]);     while (!q.empty()) {         int y = q.front() / M, x = q.front() % M;         q.pop();           for (int i = 0;i < 4;i++) {             int ny = y + dy[i], nx = x + dx[i];             if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;             if (map[ny][nx] == '.' && visit[ny][nx] == 0) {                 visit[ny][nx] = num;                 q.push(ny*M + nx);             }             else if (map[ny][nx] == 'x' && visit[ny][nx] != num) {                 if (!adjmat[num][visit[ny][nx]]) {                     adjmat[num][visit[ny][nx]] = true;                     adj[num].push_back(visit[ny][nx]);                     curr.push_back(visit[ny][nx]);                 //    printf("%d->%d\n", num, visit[ny][nx]);                 }             }         }     } } //void print() { //    for (int n = 0;n < N;n++) { //        for (int m = 0;m < M;m++) //            printf("%2d ", visit[n][m]); //        printf("\n"); //    } //} int ans[51]; int Max = 0; int dfs(int here) {     int ret = 0;     for (int &next : adj[here]) {         ret = max(ret, dfs(next) + 1);     }     if (here != 0) {         ans[ret]++;         Max = max(Max, ret);     }     return ret; } int main() {     bool flag = true;     scanf("%d%d", &N, &M);         for (int n = 0;n < N;n++) {         scanf("%s", &map[n]);         if (flag) {             for (int m = 0;m < M;m++) {                 if (map[n][m] == 'x') flag = false;             }         }     }     if (flag) { printf("-1\n"); return 0; }     for (int n = 0;n < N;n++)for (int m = 0;m < M;m++) {         if (map[n][m] == 'x' && visit[n][m] == 0) {             island(n, m);             cnt++;         }     }     for (int m = 0;m < M;m++) {         if (visit[0][m] == 0 && map[0][m] == '.') {             water(0, m, 0);         }         if (visit[N - 1][m] == 0 && map[N - 1][m] == '.') {             water(N - 1, m, 0);         }     }     for (int n = 1;n < N - 1;n++) {         if (visit[n][0] == 0 && map[n][0] == '.') {             water(n, 0, 0);         }         if (visit[n][M - 1] == 0 && map[n][M - 1] == '.') {             water(n, M - 1, 0);         }     }     if (curr.empty()) curr.push_back(visit[0][0]), adj[0].push_back(visit[0][0]);     while (!curr.empty()) {         vector<int> tmp;         for (int &n : curr) {             tmp.push_back(n);         }         curr.clear();           for (int &n : tmp) {             solve(n);         }     }     dfs(0);     for (int n = 0;n <= Max;n++) {         printf("%d ", ans[n]);     }     return 0; } Colored by Color Scripter

cs

1273 샷

1278 샷 https://www.acmicpc.net/problem/1273

N열의 맥주캔이 쌓여져있는 상태가 주어진다.
총으로 하나의 층을 없앨 수 있는데 맥주캔의 종류(검,회,흰)에따라 점수를 획득한다.
M개의 쿼리를 입력받아 해당 층을 없앨 때 점수를 구하는 문제다.

N과 M이 300,000이나 되고 하나의 열에 최대 3,000,000층 만큼의 맥주가 쌓일 수 있다.
쿼리를 받을때마다 일일이 처리하는건 절대 안되고 굉장히 크기가 큰만큼 메모리도 신경써야한다.

처음에는 segment tree와 lazy propagation로 3,000,000층에서 각층의 점수를 누적해서 저장해주었다.
근데 long long 변수로 저장하고 이러한 segment tree를 2개 저장했으니 8*16*3,000,000 byte가 필요하였다.
그래서 메모리초과가 발생하였다.

좀 생각해보니 각층의 점수 누적을 segment tree로 할 필요없이 일반배열에 저장해서 누적합하면 될것같았다.
그리고 각 층의 쿼리계산은 아까 구현해놓은 segment tree로 갖다 썼다.

사실 메모리초과 발생해서 틀리고 나서 못풀거같은 느낌이 들었는데 차분히 생각하니 답이 나왔다.
또 배열을 int형으로 1200만 선언을 해본적은 처음이고 되는사실도 오늘 알았다.
풀려서 기분이 좋다.

#include <cstdio> #include <vector> #include <algorithm> using namespace std; int N, M; int Plus[3] = { 1,2,5 }; int p[300001]; int sum[3000000]; bool chk[3000000]; struct Segment {     vector<int> tree;     int size;     Segment() {}     Segment(int N) :size(N) { tree.resize(4 * N, 0); }     int init(int node, int nl, int nr) {         if (nl == nr) return tree[node] = 1;         int mid = (nl + nr) >> 1;         return tree[node] = init(node * 2, nl, mid) + init(node * 2 + 1, mid + 1, nr);     }     void init() {         init(1, 0, size - 1);     }     int update(int idx, int val, int node, int nl, int nr) {         if (nl > idx || nr < idx) return tree[node];         if (nl == nr) return tree[node] += val;         int mid = (nl + nr) >> 1;         return tree[node] = update(idx, val, node * 2, nl, mid) + update(idx, val, node * 2 + 1, mid + 1, nr);     }     void update(int idx, int val) {         update(idx, val, 1, 0, size - 1);     }     int find(int val, int node, int nl, int nr) {         if (nl == nr) return nl;         int mid = (nl + nr) >> 1;         if (tree[node * 2] >= val) return find(val, node * 2, nl, mid);         else return find(val - tree[node * 2], node * 2 + 1, mid + 1, nr);     }     int find(int val) {         return find(val, 1, 0, size - 1);     } }; int main() {     scanf("%d", &N);     Segment seg(3000000);     seg.init();     for (int n = 0;n < 3;n++) {         for (int m = 0, in;m < N;m++) {             scanf("%d", &in);             sum[p[m]] += Plus[n];             sum[p[m] + in] -= Plus[n];             p[m] += in;         }     }     for (int n = 0;n < 3000000;n++) {         if (n != 0) sum[n] += sum[n - 1];     }     scanf("%d", &M);     for (int m = 0, in;m < M;m++) {         scanf("%d", &in);         int idx = min(3000000 - 1, seg.find(in));         if (!chk[idx]) {             chk[idx] = true;             printf("%d\n", sum[idx]);             seg.update(idx, -1);         }         else printf("0\n");     }     return 0; } Colored by Color Scripter

cs

5000 빵 정렬

5000 빵 정렬 https://www.acmicpc.net/problem/5000

1부터 N까지의 빵 번호가 주어진다.
세개의 빵을 한번에 뒤집을 수 있는데 가장 오른쪽에 있는 빵이 맨 왼쪽, 나머지는 오른쪽으로 한칸씩 밀려진다.
빵 순서를 사장이 원하는 순서로 바꿀 수 있는지 판단하는 문제다.

정답률이 85%정도 되는데 쉬운문제는 아니다.
직접 손으로 경우를 그려보니 사장이 원하는 순서의 첫번째 숫자부터 맞추면서 판단하면 해결이 가능해보였다.

두 가지 경우로 나뉘었다.

사장이 원하는 순서의 맨 앞에빵이 6번이다.
상근이의 6번빵은 5번째 index에 위치하는데 위와같이 6번빵을 당길 수 있다.
이때 사장과 상근이의 빵의 위치의 차이가 홀수인 경우에는 앞에 두 빵을 swap해서 저장해야한다.
짝수인 경우에는 swap할 필요없이 그대로 저장하면 된다.

여기까지는 생각해내는데 금방이였는데 자료구조를 어떻게 구현해야할지 한참걸렸다.
좀 복잡하지만 segment tree를 이용해 구현해냈다.

#include <cstdio> #include <vector> #include <algorithm> using namespace    std; int N; int src[100001]; int dst[100001]; int pos[100001]; struct Segment {     vector<int> tree;     int size;     Segment() {}     Segment(int N) :size(N) { tree.resize(4*N, 0); }     int update(int idx, int val, int nl, int nr, int node) {         if (idx < nl || idx > nr) return tree[node];         if (nl == nr) return tree[node] += val;         int mid = (nl + nr) >> 1;         return tree[node] = update(idx, val, nl, mid, node * 2) + update(idx, val, mid + 1, nr, node * 2 + 1);     }     void update(int idx, int val) {         update(idx, val, 0, size - 1, 1);     }     int query(int l, int r, int nl, int nr, int node) {         if (r < nl || l > nr) return 0;         if (l <= nl && nr <= r) return tree[node];         int mid = (nl + nr) >> 1;         return query(l, r, nl, mid, node * 2) + query(l, r, mid + 1, nr, node * 2 + 1);     }     int query(int l, int r) {         return query(l, r, 0, size - 1, 1);     }     int find(int val, int node, int nl, int nr) {         if (nl == nr) return  nl;         int mid = (nl + nr) >> 1;         if (tree[node * 2] >= val) return find(val, node*2, nl, mid);         else return find(val - tree[node * 2], node * 2 + 1, mid + 1, nr);     }     int find(int val) {         return find(val, 1, 0, size - 1);     } }; int main() {     scanf("%d", &N);     Segment seg(N + 1);     for (int n = 0;n < N;n++) scanf("%d", &src[n]), pos[src[n]] = n, seg.update(n, 1);     for (int n = 0;n < N;n++) {         scanf("%d", &dst[n]);         if (n >= N - 2) continue;         int idx = seg.query(0, pos[dst[n]]) - 1;         seg.update(pos[dst[n]], -1);         if ((idx) % 2 == 1) {             int g1 = seg.find(1), g2 = seg.find(2);             swap(pos[src[g1]], pos[src[g2]]);             swap(src[g1], src[g2]);         }     }     if (src[seg.find(1)] == dst[N - 2] && src[seg.find(2)] == dst[N - 1]) printf("Possible\n");     else printf("Impossible\n");     return 0; } Colored by Color Scripter

cs

다른 분들은 BIT, fenwick tree를 이용해서 짧게 푸셨는데 코드 해석을 못하겠다.