반응형
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
- dfs
- boj #19237 #어른 상어
- 처우산정
- 물채우기
- 성적평가
- msSQL
- 파라메트릭
- 처우협의
- Docker
- 오퍼레터
- compose
- 소프티어
- 연결요소
- 경력
- BFS
- BOJ
- incr
- Kafka
- @P0
- 퇴사통보
- 13908
- 6987
- 이분탐색
- 기술면접
- 백준
- softeer
- 백트래킹
- OFFSET
- 매개변수탐색
- upper_bound
Archives
- Today
- Total
기술 블로그
홈 방범 서비스 본문
728x90
반응형
https://www.swexpertacademy.com/main/solvingProblem/solvingProblem.do
저번 코드 : https://hsdevelopment.tistory.com/45
다시 풀어보았다.
처음에 시간 초과 나길래
이유가 뭔가 했더니
하나의 점에 대하여, BFS를 몇 십 번이나 반복하고 있었던 것이었다.
그리고 각 그 경우마다 처음부터 끝까지 BFS를 또 돌리고 있었다.(아래 짧은 코드 참고)
1 2 3 4 5 | for(int k = 0; k < 2 * N; k++) for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) ans = max(ans, bfs(i, j, k)); | cs |
그래서 생각해보니 그냥
하나의 점을 처음부터 끝까지 BFS를 돌리면서
변수 k에 대해 그 때 그 때 마다, 계산해주면 됐었다.
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 | #include <bits/stdc++.h> using namespace std; int N = 0, M = 0, Map[22][22] = { 0, }; int dy[4] = { 0, 1, 0, -1 }; int dx[4] = { 1, 0, -1, 0 }; int bfs(int r, int c) { int ret = 0, k = 0, home = 0; bool visit[22][22] = { false, }; memset(visit, false, sizeof(visit)); queue<pair<int, int> > q; q.push({ r, c }); visit[r][c] = true; while (!q.empty() || k <= N + 10) { int qSize = q.size(), pft = 0; pft = home * M - (k*k + (k - 1)*(k - 1)); if (pft >= 0) ret = max(ret, home); while (qSize--) { int y = q.front().first; int x = q.front().second; q.pop(); if (Map[y][x] == 1) ++home; for (int i = 0; i < 4; i++) { int ny = y + dy[i]; int nx = x + dx[i]; if (ny < 0 || ny >= N || nx < 0 || nx >= N || visit[ny][nx]) continue; visit[ny][nx] = true; q.push({ ny, nx }); } } ++k; } return ret; } int main(void) { int T = 0; scanf("%d", &T); for( int tc = 1; tc <= T; tc++ ) { int ans = -1; scanf("%d %d", &N, &M); for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) scanf("%d", &Map[i][j]); for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) ans = max(ans, bfs(i, j)); printf("#%d %d\n", tc, ans); } return 0; } | cs |
728x90
반응형
'알고리즘 문제 > SW Expert Academy' 카테고리의 다른 글
5650. [모의 SW 역량테스트] 핀볼 게임 (0) | 2019.10.10 |
---|---|
5656번 벽돌 깨기 (0) | 2019.07.01 |
1767번 프로세서 연결하기 (0) | 2019.04.14 |
5653번 줄기세포 배양 (2) | 2018.10.05 |
2477번 차량 정비소 (0) | 2018.09.14 |