백준34 [BOJ]1261번: 알고스팟 문제: https://www.acmicpc.net/problem/1261 다익스트라 문제입니다. 단순 BFS로 벽을 뚫을 때마다 방문표시를한다면 visit[10000][100][100]으로 메모리 초과가 날 것입니다. 중복해서 방문을 하지 않도록 조건을 걸어보자면, visit[y][x] : (y,x) 칸을 방문했을 때 부순 벽의 갯수 위와 같이 방문배열을 정의하고 now.BROEKN < visit[y][x].BROKEN 조건일 때만 방문할 수 있도록 갱신해주면 최소한으로 벽을 부순 상태로만 계속 탐색을 할 수 있습니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1261.cc 2020. 5. 21. [BOJ]18290번: NM과 K(1) 문제: https://www.acmicpc.net/problem/18290 완전 탐색문제입니다. 맨 처음에 문제를 잘못 이해해서 헤맸었네요. 주어진 NM 칸에 대해 최대 4칸을 뽑고 그 칸이 인접해있는지 확인하면 되는 문제입니다. 두 가지만 처리하면 해결할 수 있는 문제입니다. 1. 100 콤비네이션 K만큼의 경우의 수를 생성한다. (NM의 상한이 100이니, 최대 100 콤비네이션4 만큼 경우의 수가 뽑히겠네요.) 2. 뽑은 K칸들이 인접한지 확인한다. 3. 인접하지 않다면 SUM을 구해 최댓값을 갱신한다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ18290.cc 2020. 5. 20. [BOJ]16957번: 체스판 위의 공 문제: https://www.acmicpc.net/problem/16957 유니온 파인드 문제입니다. BFS로 문제를 접근한다면 O(R^2*C^2) 으로 시간초과가 납니다. 주변에 인접한 칸 중에 가장 작은 칸 A를 루트라고 생각해봅시다. 그러면 A칸과 인접한 모든 칸은 A를 부모로 가지고 있습니다 즉, parent[SUM_NODE] = A 이런식입니다. 이런식으로 우선 R*C만큼 돌면서 각 노드가 부모로 가지는 노드가 무엇인지 find연산을 해줍니다. 그러면 자기 자신이 가장 작은 칸은 parent[NODE] = NODE가 될것이고, 자기보다 작은 칸이 존재한다면 parent[NODE] = MORE_SMALL_NODE가 될 것입니다. 이 다음엔 진짜 루트 노드를 구하러 갑니다. 무슨 말이냐면 누군가에겐.. 2020. 5. 19. [BOJ]17822번: 원판 돌리기 문제: https://www.acmicpc.net/problem/17822 시뮬레이션 문제입니다. 원판의 숫자와 인접한 컴포넌트를 확인할 때 1번인덱스와 M번 인덱스의 숫자도 4방향 탐색을 할 수 있도록 인덱스를 조정하는 게 중요합니다. 또한, 평균값은 실수로 구해줘서 대소비교를 해주도록 하면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ17822.cc 2020. 5. 15. 이전 1 ··· 5 6 7 8 9 다음
