1. priorities 배열을 우선순위 큐에 넣는다. 2. priorities 배열의 값과 배열의 인덱스 (location)를 pair로 하여 큐에 넣는다. 3. 큐가 empty가 아닐 때까지 while문을 돌면서, 우선순위 큐와 큐에서 각각 poll을 해준다. -> 우선순위 큐에서 poll된 값 ! = 현재 poll된 큐 의 우선순위 라면, poll했던 큐를 다시 넣고 큐에서 계속 poll -> add를 반복한다. ( 해당 우선순위의 요소가 나올 때 까지) 4. queue 에서 최종적으로 poll된 값의 location과 우리가 찾을 요소의 location이 같다면 종료해준다. import java.util.*; class pair{ int loc; int prior; public pair(int l..
11559번: Puyo Puyo 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) www.acmicpc.net 뿌요뿌요의 규칙 상.하.좌.우 4개의 같은 색깔의 뿌요가 모이면 모두다 터진다. 뿌요는 중력에 따라서 빈공간이 생기면 무조건 아래로 이동해야한다. 여러색의 뿌요는 동시에 같은 연쇄에서 터질 수 있다. 세번째 조건은 백준의 유명한 BFS 문제인 토마토를 떠올릴 수 있다 .그러하다 나는 이 문제가 시뮬레이션이 들어간 토마토라고 생각했다. 물론 뿌요뿌요는, 상.하.좌.우 모두 무조건 터지는게 아니라 '같은 색'이어야만 터질 수 있으므로 BFS와 DFS를 모두 사용가능 하기도 하다. 그러면 일단 나의 로직은 이러하다. 모든 색깔의 뿌요를 큐에 넣는다. 이 ..
2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 주의해야 할 점 * 벽을 부쉈지만 최단경로가 아닌 경로와, 벽을 부수지 않는 최단 경로에서 경로가 서로 겹칠 경우, 제대로된 최단 경로를 구할 수 없게 된다. 이를 꼭 신경써주어야 한다. 해당 문제는 bfs를 사용하지만, 큐에 넣을 요소들이 더 추가되었고, 방문 내역을 저장하는 visit 배열이 true false 가 아니라, int 형으로 선언을 해서 해당 노드가 벽을 부순 경로에 포함되는지, 벽을 부수지 않아본 경로에 포함되는지 ..
15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net 처음에는 2차원 배열형태로 값이 주어져서 당연히 dfs나 bfs로 푸는 문제인줄 알았으나, 이 문제는 조합 알고리즘으로 푸는 문제였다. 조합 알고리즘만 있다면 매우 간단하게 구할 수 있다. 로직을 간단..