그래프탐색

https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net [문제] [풀이] 물이 찰 예정엔 고슴도치가 이동불가 => 물 먼저 처리할 것. 즉 , 탐색을 하기위해 우선순위를 1. 진행일수 2. 처리순서 로 하기위해서 우선순위큐를 이용한 BFS로 탐색하였다. 물탐색 : map이 '.' 이거나 'S' 인 경우에만 진행후 , '*'로 마킹. 고슴도치탐색 : map이 '.' 이거나 'D' 인 경우에만 진행후 'S'로 마킹. 1 2 3 4 5 6 7 8 9 10 11 12 1..

https://programmers.co.kr/learn/courses/30/lessons/43164# 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr [문제] [풀이] 그래프 탐색문제이다. 처음엔 TreeMap과 같이 티켓과 정보를 한번에 저장해서 하려했으나 , 키중복에서 꼬이거나 다중 Map을 써야하는 상황이 나오는 등 쉽지 않았기때문에 티켓자체를 방문지점으로 써버렷다. 그래서 티켓의 사용여부를 boolean 타입의 visit 배열로 사용했고 그냥 완전탐색 + 백트래킹으로..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 풀이 상어 기준으로 bfs 탐색 시작하여 거리가 가장 가까운 물고기를 priorityQueue에 먼저 넣는다. 탐색이 끝났을 때 , 큐의 맨 앞에 있는것을 먹거나 물고기가 없을 경우엔 종료하면 끝. 큐에 담는 이유 1. 거리가 가까운 순 2. 같은 거리에 있는 것이 여러개 있으면 좌표평면상 1.위쪽 -> 2.왼쪽 우선순위로 먹음.(이게 중요) bfs 탐색으로 위,왼쪽을 먼저 하는게 아..

https://www.acmicpc.net/problem/16930 16930번: 달리기 진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다. 체육관은 1×1 크기의 칸으로 나누어져 있고, 칸은 빈 칸 또는 벽이다. x행 y열에 있는 칸은 (x, y)로 나타낸다. 매 초마다 진영이는 www.acmicpc.net 문제 풀이 이 문제에서 내가 집은 포인트는 3 가지이다. 1. 우선 순위 큐를 이용하여 최대한 시간이 덜 걸리는 순으로 처리하는 것 (우선순위큐 bfs 다익스트라 이용) 2. dp배열을 이용해서 이미 왔던 곳이면 break를 거는 것 3. 이중 for 문을 이용해서 nextX,nextY를 정할 때 , 1부터~k까지 이동가능한 모든 경우를 큐에 넣는 것 1 2 3 4 5 6 7 8 9 1..

문제 풀이 이 문제에서 집어야 할 포인트는 세 가지다. 1. 3차원 visit[][][] 배열을 사용하여 열쇠를 먹을때 마다 visit[][][index++] 을 처리해줘서 열쇠 먹은시점이랑 열쇠를 안 먹은 시점이랑 분리 시키는 것. 2. BFS를 위해 집어 넣을 노드인 'Point' 에 대해 Comparable을 구현하여 열쇠를 가장 많이 먹은 시점이 우선 탐색할 수 있도록 해주는것. 3. 우선순위 큐인 PriorityQueue를 사용할 것. 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 ..

문제 풀이 이 문제에서 집어야 할 포인트는 두 가지다. 1. BFS를 활용한 우선순위 큐(PQ)를 이용하여 PQ안의 원소를 처리할 때 먼 산으로 가지 않게 하는 것. 2. 어느 위치(cur)로 갔을 때, 몇 번 만에 갔는지를 기록하여 (distance[] 배열) 무한 루프로 빠지지 않게 하는 것. => 즉 , if(distance[cur+e] > distance[cur]+ 1) { distance[cur+e] = distance[cur]+ 1; q.add(e + cur); } 이 식이 성립해야 하는데, 여기서 cur은 현재위치이고 , e 는 up 또는 down 버튼을 눌렀을 때의 증감치다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..

문제 풀이 생각보다 간단한 문제이다 . 끊어질 노드를 C 라고 하자. 그래프를 ArrayList 배열로 만든 뒤 끊어질 노드'C'의 위치까지 처음부터 다 받아서 그래프를 단방향으로 연결할 때 C가 나오면 연결을 안 해주면 끝. root 부터 DFS 돌리면서 ArryList의 size가 0이면 leaf 노드이다. 입력 노드'e' 를 받을때 3가지의 경우로 나눌 수 있는데 1. e 가 root 일때 => e == -1 2. e 가 끊어질 노드 'C' 이거나 연결하려는 노드의 부모노드가 'C'일때 => ( e==C || i ==C ) 3. 그외 경우엔 단방향 연결 단방향으로 연결이 완성된 그래프를 root 부터 DFS 재귀호출을 이용하여 자식이 없는 노드를 카운트하면 끝. 이때 , 끊어질 노드 'C'가 roo..

이 문제는 DFS + DP 문제이다. 여기서 DP는 최대 생존가능일 수를 기록. 기본적으로 , 입력을 map으로 받았을때, 다음 이동해야 하는 방향의 값이 지금의 값보다 더 커야한다. 즉 , map[y][x] < map[nextY][nextX] 가 성립 해야 한다. 그리고 탐색했던곳을 중복탐색하는 것을 막기위해 메모이제이션 기법으로 dp를 바로 반환해주는것이 핵심이다. 그렇지 않으면 시간초과 발생. if(dp[y][x] != 1) return dp[y][x]; dfs로 탐색했을때 , 현재 기록된 생존가능일 수 보다 더 오래 살 수 있으면 갱신. dp[y][x] = Math.max(dfs(nextX,nextY)+1,dp[y][x]); 처음에 바로 떠 올리기엔 쉽지 않은 문제이다. 12345678910111..