일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 오퍼레터
- BOJ
- 성적평가
- softeer
- 백준
- 13908
- 경력
- 소프티어
- 물채우기
- compose
- boj #19237 #어른 상어
- 이분탐색
- 연결요소
- Kafka
- @P0
- dfs
- 처우산정
- 6987
- 처우협의
- BFS
- upper_bound
- 백트래킹
- OFFSET
- Docker
- 파라메트릭
- 매개변수탐색
- 퇴사통보
- 기술면접
- incr
- msSQL
- Today
- Total
기술 블로그
16957번 체스판 위의 공 본문
https://www.acmicpc.net/problem/16957
# 시간초과 # 복습 # 구현 # 생각 # 아이디어 # 유니온 # 파인드 # Find # 경로 # 압축 # Union
처음 구현했을 때, 시간 초과가 발생했다.
이 문제의 핵심은 경로 압축(Path Compression)이다.
간단하게 말하자면,
30에서 계속 최솟값을 통해 가다가 2로 도착하였다면,
또 다른 숫자인 50에서 출발하여 최솟값을 통해 계속 진행하다가 30을 만나면 더이상 진행할 필요가 없다는 뜻이다.
즉, 30에서 이미 2로 도착하였기 때문이다.
이 문제는 Union-Find에서 Find를 활용하는 문제이다.
예제 1로 설명을 하겠다.
우선 예제 1을
1 3 4
5 6 7
8 9 2
이렇게 접근하지 말고, 아래와 같이 접근을 해보자.
숫자 내용 자체를 바꾸자는 뜻이 아니라,
1이 있는 자리 (0, 0)에 0번을 부여
3이 있는 자리 (0, 1)에 1번을 부여
4가 있는 자리 (0, 2)에 2번을 부여
.
.
.
라는 의미이다.
번호를 부여할 때는 현재 좌표(r, c)에 대하여 r*C + c로 하면 된다.
C는 입력값(열의 길이)
그런 다음 모든 좌표에 대하여 인접한 좌표들(자신 포함)의 최솟값을 찾는 과정을 한 번만 실행해보자.
그리고 화살표를 표시해보자.
작은 값 ← 큰 값
p[큰 값] = 작은 값
예를 들어, 1의 인접한 주변에는 3, 5, 6, 1(자신)이 있고, 최솟값은 1이다. 즉, 자기 자신이다.
1 ← 1
이것을 부여한 번호로 표시하면, [0] ← [0]이다.
p[0] = 0;
3의 주변에는 1이 최솟값이고, 1 ← 3이다.
부여한 번호로 표시하면, [0] ← [1]이다.
p[1] = 0;
.
.
.
계속 진행하면, 아래와 같은 결과가 나온다.
위의 그림을 보면 바로 생각이 떠오를 것이다. Union-Find
한 번만 진행한 다음, Find 함수를 통해 Find 값을 인덱스로 하는 배열인 ans의 값을 1을 증가시키면 된다.
++ans[Find(i*C + j)];
다시 말하면,
[0], [1], [2], [3], [4], [6]을 진행하면, Find는 0을 return할 것이고, 이에 대한 ++ans[0];을 수행하여 최종적으로 6이 나올 것이다.
시간 초과
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 | #include <bits/stdc++.h> using namespace std; #define Max 505 #define INF 2e9 int m[Max][Max], ans[Max][Max], R, C; int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 }; int dx[8] = { 1, 1, 0, -1, -1, -1, 0, 1 }; vector<pair<int, int> > v; // 인접한 숫자들과의 비교((r, c) 위치에 있는 숫자가 제일 작은지) bool isSmallest(int r, int c) { for (int i = 0; i < 8; i++) { int y = r + dy[i]; int x = c + dx[i]; if (y < 0 || y >= R || x < 0 || x >= C) { continue; } if (m[r][c] > m[y][x]) { return false; } } return true; } void print() { printf("\n===================\n"); for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { printf("%d ", ans[i][j]); } printf("\n"); } printf("\n"); } void simulation() { while (true) { bool stop = true; for (auto &i : v) { // 현재 위치에 있는 숫자가 가장 작으면 if (isSmallest(i.first, i.second)) { continue; } // 아래 실행 여부 stop = false; int r = i.first, c = i.second; int y = 0, x = 0; // 이동해야한다면 가장 작은 숫자가 있는 칸으로 이동 int Min = INF, diry = 0, dirx = 0; for (int d = 0; d < 8; d++) { y = r + dy[d]; x = c + dx[d]; if (y < 0 || y >= R || x < 0 || x >= C) { continue; } // 이동 방향 저장 // dy, dx임을 주의 if (Min > m[y][x]) { Min = m[y][x]; diry = dy[d]; dirx = dx[d]; } } y = r + diry; x = c + dirx; ++ans[y][x]; // 이동할 칸 --ans[r][c]; // 원래 위치 칸 i.first = y; // 저장 i.second = x; // 저장 } if (stop) { break; } } } int main() { cin.tie(0); scanf("%d %d", &R, &C); for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { scanf("%d", &m[i][j]); v.push_back({ i, j }); ans[i][j] = 1; } } simulation(); for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { printf("%d ", ans[i][j]); } printf("\n"); } return 0; } | cs |
정답
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 | #include <bits/stdc++.h> using namespace std; #define Max 505 #define INF 2e9 int m[Max][Max], p[Max * Max], ans[Max * Max], R, C; int dy[9] = { 0, 1, 1, 1, 0, -1, -1, -1, 0 }; // 자신 포함(0, 0) int dx[9] = { 1, 1, 0, -1, -1, -1, 0, 1, 0 }; // 자신 포함 int Find(int x) { if (x == p[x]) return x; return p[x] = Find(p[x]); } int main() { cin.tie(0); scanf("%d %d", &R, &C); int idx = 0; for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { scanf("%d", &m[i][j]); } } // 우선 한 번만 진행 for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { int Min = INF, ey = 0, ex = 0; for (int k = 0; k < 9; k++) { int y = i + dy[k]; int x = j + dx[k]; if (y < 0 || y >= R || x < 0 | x >= C) { continue; } // 가장 작은 값을 찾는다. if (Min > m[y][x]) { Min = m[y][x]; ey = y; ex = x; } } // 부모 표시 p[i*C + j] = ey*C + ex; } } for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { ++ans[Find(i*C + j)]; } } for (int i = 0; i<R; i++) { for (int j = 0; j<C; j++) { printf("%d ", ans[i*C + j]); } printf("\n"); } return 0; } | cs |
'알고리즘 문제 > BOJ' 카테고리의 다른 글
16925번 문자열 추측 (0) | 2020.02.29 |
---|---|
3197번 백조의 호수 (0) | 2020.02.29 |
18511번 큰 수 구성하기 (0) | 2020.02.28 |
16958번 텔레포트 (0) | 2020.02.27 |
16954번 움직이는 미로 탈출 (0) | 2020.02.27 |