반응형
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
- boj #19237 #어른 상어
- 처우산정
- OFFSET
- 백준
- softeer
- 13908
- BOJ
- upper_bound
- 물채우기
- 퇴사통보
- msSQL
- @P0
- 기술면접
- 경력
- 연결요소
- 처우협의
- 성적평가
- 6987
- incr
- 파라메트릭
- 소프티어
- 이분탐색
- Docker
- 오퍼레터
- compose
- dfs
- BFS
- Kafka
- 매개변수탐색
- 백트래킹
Archives
- Today
- Total
기술 블로그
2933번 미네랄, 18500번 미네랄 2 본문
728x90
반응형
https://www.acmicpc.net/problem/2933
https://www.acmicpc.net/problem/18500
bfs dfs sw역량테스트 삼성 코딩테스트 코테 코딩 필수 복습 추천 구현 simulation boj 백준 시뮬레이션 연결요소의 개수
2933번(미네랄)과 18500번(미네랄2)은 거의 같은 문제라고 할 수 있다.(사실 정확한 문제 구분은 모르겠음.)
핵심은 아래 3가지인 것 같다.
1. DFS를 이용한 연결 요소의 활용(Group을 지을 줄 아는가? 즉, Grouping(그루핑))
2. BFS를 통한 각 그룹에서 다른 그룹 또는 맨 밑까지의 거리들 중의 최솟값
3. x를 아래로 이동시키기(구현력) → 나는 임시배열(t)을 활용
참고로 행, 열을 (0 ~ R - 1, 0 ~ C - 1)표현하였기 때문에 입력으로 주어지는 막대를 던지는 높이는 R - stick이라고 할 수 있다.
예시)
왼쪽이 입력으로 주어지는 막대의 높이
오른쪽이 그 높이를 내가 생각하는 배열에서의 행(위치)
8 → 0
7 → 1
6 → 2
5 → 3
4 → 4
3 → 5
2 → 6
1 → 7
temp 배열은 각 x를 같은 그룹끼리는 같은 번호(gn)를 표시한 것이다.
나머지는 코드 안의 주석을 참고.
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 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 | #include<bits/stdc++.h> using namespace std; #define Max 103 int R, C, n; int dy[4] = { 0, 1, 0, -1 }; int dx[4] = { 1, 0, -1, 0 }; char m[Max][Max]; bool visit[Max][Max]; // 방문 여부 vector<int> stick; // 막대기 높이 // 한 그룹(num)에서 다른 그룹(!= num) 또는 맨 밑으로 이동할 수 있는 거리들 중 최솟값 int bfs(int num, int temp[][Max], queue<pair<int, int> > &q) { int ret = 0; // 반환할 거리 while (!q.empty()) { int qs = q.size(); while (qs--) { int r = q.front().first; int c = q.front().second; q.pop(); // 마지막에 도달했으면 return if (r == R - 1) { return ret; } // 다음 칸이 'x'이면서 같은 그룹이 아니라면(temp의 숫자가 달라야 한다.) return else if (r + 1 < R && m[r + 1][c] == 'x' && temp[r + 1][c] != num) { return ret; } // 아래로만 이동하기 때문에 따로 방문 처리가 필요 없다. if (r + 1 < R && temp[r + 1][c] != num) { q.push({ r + 1, c }); } } ++ret; } return ret; } void dfs(int r, int c, int gn, int temp[][Max], vector<pair<int, int> > &vt) { visit[r][c] = true; // 방문 처리 temp[r][c] = gn; // x의 위치를 고려하여, Group을 기록한다. 같은 그룹이면 같은 gn(그룹 번호)이다. vt.push_back({ r, c }); // 같은 그룹끼리 좌표를 활용해야하기 때문에 vt에 담아야 한다. for (int i = 0; i < 4; i++) { int y = r + dy[i]; int x = c + dx[i]; if (y < 0 || y >= R || x < 0 || x >= C || visit[y][x] || m[y][x] == '.') { continue; } dfs(y, x, gn, temp, vt); } } void chk() { memset(visit, false, sizeof(visit)); int cnt = 0, temp[Max][Max] = { 0 }; vector<vector<pair<int, int> > > v; for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { vector<pair<int, int> > vt; // 연결 요소 if (!visit[i][j] && m[i][j] == 'x') { dfs(i, j, cnt + 1, temp, vt); ++cnt; } // 비어있지 않으면 x가 있다는 뜻이므로, v에 담는다. if (!vt.empty()) { v.push_back(vt); } } } int num = 1; for (auto i : v) { queue<pair<int, int> > q; // 각 그룹에 따른 좌표들을 queue에 담는다. for (auto j : i) { q.push({ j.first, j.second }); } int dist = bfs(num, temp, q); // 0이 아니라는 것은 아래로 떨어질 위치가 있다는 것이다. if (dist != 0) { // 임시 배열 char t[Max][Max]; for (auto j : i) { // 새로운 위치(행 + dist)에 원래(행)의 값을 넣는다. t[j.first + dist][j.second] = m[j.first][j.second]; m[j.first][j.second] = '.'; // 원래 좌표는 없앤다. } for (auto j : i) { // 새로운 위치를 활용 m[j.first + dist][j.second] = t[j.first + dist][j.second]; } // 둘 이상의 클러스터가 떨어질 일은 없기 때문에 break가 가능하다. break; } ++num; } } void simulation() { for (int i = 0; i < n; i++) { int r = R - stick[i]; if (i % 2) { // 홀수(오른쪽에서 왼쪽으로 던짐) for (int j = C - 1; j >= 0; j--) { if (m[r][j] == 'x') { m[r][j] = '.'; chk(); // 하나 씩 없어질 때마다 검사 break; // 1개만 없어진다.(문제 조건) } } } else { // 짝수(왼쪽에서 오른쪽으로 던짐) for (int j = 0; j < C; j++) { if (m[r][j] == 'x') { m[r][j] = '.'; chk(); // 하나 씩 없어질 때마다 검사 break; // 1개만 없어진다.(문제 조건) } } } } // 정답 출력 for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { printf("%c", m[i][j]); } printf("\n"); } } int main() { //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin); cin.tie(0); cin >> R >> C; for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { cin >> m[i][j]; } } cin >> n; stick.assign(n, 0); for (int i = 0; i < n; i++) { cin >> stick[i]; } simulation(); return 0; } | cs |
728x90
반응형
'알고리즘 문제 > BOJ' 카테고리의 다른 글
13308번 주유소 (0) | 2020.04.15 |
---|---|
1506번 경찰서 (0) | 2020.04.14 |
18870번 좌표 압축 (0) | 2020.04.11 |
10999번 구간 합 구하기 2 (0) | 2020.04.10 |
1480번 보석 모으기 (0) | 2020.04.09 |