본문 바로가기

queue

 (8)
[Baekjoon] 백준 1240번: 노드 사이의 거리 (JAVA) 문제 1240번 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net [ 문제 풀이 ] 무향 그래프로 각 노드를 연결하는 ArrayList[]에 저장하고, 두 정점 사이의 거리를 구하는 문제입니다. Node 클래스를 정의하여 각 정점 값들과 거리를 저장합니다. BFS 탐색을 활용하여 Queue에 다음 방문할 위치와 거리를 저장하고 탐색하며 거리를 계속 더해주면 됩니다. 무향 그래프이므로 visit[]을 사용하여 방문한 정점인지 체크해줍니다. [ 코드 ] import java.io.*; impor..
[Baekjoon] 백준 2234번: 성곽 (JAVA) 문제 2234번 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net [ 문제 풀이 ] 1) 방의 개수 / 가장 넓은 방의 넓이 구하기 이 문제에서 벽에 대한 정보를 얻기 위해서는 비트 연산을 이용해야 합니다. 각 4방향(서, 북, 동, 남)이 2^0, 2^1, 2^2, 2^3으로 더해지기 때문에, &와 = N) continue; if (visit[nextR][nextC]) continue; visit[nextR][nextC] = true; queue.offer(new Node(nextR, nextC)); }..
[Baekjoon] 백준 1388번: 바닥장식 (JAVA) 문제 1388번 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나 www.acmicpc.net [ 문제 풀이 ] 같은 바닥 장식끼리 한 묶음으로 묶어서 몇 개의 묶음이 있는지 카운트를 해주면 되는 문제입니다. 이중 for()문을 순회하며 방문하지 않은 곳인 경우 카운트를 하나 증가시키고 BFS를 돌아 나무 판자의 무늬에 따라 같은 행 또는 열로 이동하며 같은 무늬인 곳들을 탐색해주면 됩니다. [ 코드 ] import java.io.*; import java.util.LinkedList; import java.util.Queue; import ja..
[Baekjoon] 백준 21924번: 도시 건설 (JAVA) 문제 21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net [ 문제 풀이 ] 모든 건물을 최소한의 비용으로 연결하는 문제이므로 크루스칼 알고리즘으로 풀면 됩니다. 크루스칼 알고리즘에 대한 자세한 설명은 아래 포스트를 참고해주세요 :) [JAVA] 서로소 집합(Disjoint Sets)과 연산 최근 알고리즘 문제를 풀면서 최소 신장 트리 개념에 대해 공부하다가 알게 된 크루스칼 알고리즘..
[Baekjoon] 백준 14567번: 선수과목 (JAVA) 문제 14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net [ 풀이 과정 ] 대표적인 위상 정렬 문제입니다. 위상정렬 문제는 아래의 내용을 기본으로 해서 풉니다. 1. 방향 그래프를 만든다. (연결 리스트 생성) 2. 각 노드의 진입차수를 배열로 저장한다. 3. 진입차수가 0인 노드를 그래프에서 하나씩 지워가며 queue에 저장한다. 학기는 depth로 생각할 수 있으므로, 큐의 현재 사이즈만큼 돈 후에 하나씩 증가시켜주면 됩니다. 문제에 나와있는 예제 입력 2를 보면 아래와 같습니다. 진입차수가 0인 노드 1, 4, 6을 먼저 q..
[Baekjoon] 백준 11123번: 양 한마리... 양 두마리... (JAVA) 문제 11123 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net [ 풀이 과정 ] 양들의 무리만 카운트하면 되므로 map[][]에 양과 풀을 저장한 후 for()문으로 순회하면서 '#' 가 있는 위치에서 카운트를 하나 증가시키고, bfs()를 돌려주면 상하좌우로 붙어있는 '#' 끼리 최대한 방문하게 됩니다. (행, 열의 최대 크기가 각각 100이므로 시간복잡도는 충분합니다.) !! for()문으로 순회할 때 방문체크까지 해주어야 정점을 중복해서 방문하지 않게 됩니다. [ 코드 ] import..
[Baekjoon] 백준 14248번: 점프 점프 (JAVA) 문제 14248 14248번: 점프 점프 첫 번째 줄에는 돌다리의 돌 개수 n이 주어진다.(1≤n≤100,000) 돌의 번호는 왼쪽부터 1번에서 n번이다. 다음 줄에는 그 위치에서 점프할 수 있는 거리 Ai가 주어진다.(1≤Ai≤100,000) 다음 줄에는 출 www.acmicpc.net [ 풀이 과정 ] 입력값을 살펴보면, 돌의 개수를 입력받은 후 각 돌의 위치에서 좌우로 점프할 수 있는 거리, 즉 칸의 개수를 입력받습니다. 따라서 jump[]에 각 위치에서 점프할 수 있는 거리를 입력 받아 저장해주고, BFS를 사용하여 현재 칸에서 점프하여 갈 수 있는 모든 위치를 큐에 넣고 방문표시를 해준 후, 전역변수 cnt를 하나씩 증가해줍니다. [ 코드 ] import java.io.*; import java..
[SWEA] 3000. 중간값 구하기 (with JAVA) 문제 3000 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 중간값을 구하는 방법 중에서 우선순위 큐 (Priority Queue)를 사용해보겠습니다. 삽입할 때마다 중간값을 구하는 문제로, Heap 으로 구성된 Priority Queue 를 사용합니다. 시간 복잡도는 O(nlogn) 입니다. 중간값을 구하기 위해서는 아래와 같은 규칙을 따라야 합니다. 1. 제일 처음에는 최대 힙에 삽입 2. 최대 힙의 크기는 최소 힙의 크기와 같거나 하나 더 큼 3. 최대 힙의 최대 원소는 최소 힙의 최소 원소보다 작거나 같음. 즉, 최대 힙의 루트 노드

티스토리툴바