본문 바로가기

백준알고리즘15

[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]1194번: 달이 차오른다, 가자. 문제: https://www.acmicpc.net/problem/1194 비트 연산자 + BFS 문제입니다. A~F는 6개의 문자로 {공집합, ... , {a,b,c,d,e,f} } 까지의 부분집합은 2^6 = 64개로 나타낼 수 있습니다. 총 64개의 state가 존재한다고 표현하겠습니다. 그래서 [64][N][M] 만큼의 방문(상태)배열이 존재하게 됩니다. 그러면 각 칸을 순회할 때 가지고 있어야 할 정보는 아래와 같이 네 가지 정보입니다. { 현재 STATE(0~64), Y좌표, X좌표, MOVE_CNT } 열쇠칸을 만났다면 OR 연산자를 통해 현재 STATE에 특정 열쇠를 더해줍니다. int NEW_STATE = NOW_STATE | (1 2020. 5. 17.

티스토리툴바