알고리즘7 백준 9376 탈옥 https://www.acmicpc.net/problem/9376 9376번: 탈옥 문제 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 � www.acmicpc.net 이 문제는 공부 삼아 블로그를 참고해서 풀었다 (https://stack07142.tistory.com/145 님 블로그) 정말 혼자서는 생각도 못 해낼 방법인 듯... 많이 배웠다! 기본 기본적으로 이 문제에서 가중치는 연 문의 개수이다 (Pos 객체의 door변수로 체크) visit 배열을 방문/미방문이 아니라 몇 개의 문을 열어 해당 지점에 도착했는지를 기록한다 더 적은 가중치(연 문의 수)로 해당 .. 2020. 5. 21. SWEA 2112 보호필름 백트래킹 가지치기를 잘 해야 시간초과가 나지 않는다 한 열이 실패하면 그 경우는 무조건 실패다 → return false 한 열에서 k개 이상이 되면 그 열은 성공이다 → continue loop 해서 다음 열 탐색으로 넘어가자 0개부터 개수를 늘려가며 투여하므로 앞에서 답이 나왔다면 (ans≠-1) break하고 출력한다 알고리즘 1. 어떤 행에 약품을 투여할지 조합으로 정한다 (0개 ~h-1개) - h-1개까지 해서 안 되면 h개 투여해야하는 거니까 예외처리로 출력해준다 - 새로운 dfs마다 memcpy를 해준다 2. 0개부터 개수를 늘려가며 투여하므로 앞에서 답이 나왔다면 (ans≠-1) break하고 출력한다 3. 조합을 돌리면서 재귀 전 insert, 재귀 후 delete로 약품 투여를 처리해준.. 2020. 5. 20. Kruskal Kruskal MST를 만드는 알고리즘 중 하나이다 간선이 많을 때 사용하면 Prim 알고리즘보다 성능이 좋다 수도 코드 1.Edge 클래스 생성 & edgeList 생성 2.union-find 메서드들 생성 findSet, isSameParent, union 3.makeSet 4.간선의 가중치 기준 오름차순 정렬 5.모든 간선을 탐색하며 다른 집합에 속하면 sum갱신 & union 자바로 구현한 Kruskal public class Kruskal { static class Edge implements Comparable{ int a, b, cost; public Edge(int a, int b, int cost) { super(); this.a = a; this.b = b; this.cost = cos.. 2020. 5. 19. 백준 16137/SWEA 4727 견우와 직녀 건널 수 있는지 여부 확인 방법 쉬는 시간엔 건널 수 없다! 대기하는 걸 구현하지 않고 이미 대기한 후의 시간(nt)을 계산해서 큐에 넣는다 int waitTime = map[nx][ny] 또는 m (원래 오작교인지 새로 짓는 오작교인지 여부에 따라) int nt = t + (waitTime - (t%waitTime); BFS 건널 수 있는 경우(길, 오작교)와 없는 경우(절벽)으로 나눈다 건널 수 있는 경우 길 ⇒ 일반 BFS 오작교 : 이전에 건넌 적 없었는지 확인 없는 경우 : 새로운 오작교를 만들 수 있는가를 확인! 직전 칸(map[x][y])이 오작교였던 경우 불가 교차하는 곳은 불가 : 포문 돌리며 가로와 세로에 있는 1의 개수를 세어 둘 다 1 이상이면 불가 BFS 코드 static void.. 2020. 5. 16. 이전 1 2 다음
