너비우선탐색

[백준] 17197. Fence Planning (Java)

문제 17197번: Fence Planning Farmer John's $N$ cows, conveniently numbered $1 \ldots N$ ($2 \leq N \leq 10^5$), have a complex social structure revolving around "moo networks" --- smaller groups of cows that communicate within their group but not with other groups. Each cow is situate www.acmicpc.net 알고리즘 그래프, 너비우선탐색(BFS) 풀이 그룹을 판별하지 않은 각 소를 시작으로 그래프를 탐색해 묶인 소들의 miny, minx, maxy, maxx 좌표를 찾는다. 울타리는..

[백준] 21736. 헌내기는 친구가 필요해 (Java)

문제 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 알고리즘 그래프, 너비우선탐색(BFS) 풀이 도연이의 위치 (x,y)에서 시작하여 상하좌우로 너비우선탐색을 진행하며 만난 사람(P)의 수를 센다. 이때, 그래프에 P를 O로 바꾸어 입력해야함에 주의한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java...

[백준] 16940. BFS 스페셜 저지 (Java)

문제 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 알고리즘 그래프, 너비 우선 탐색(BFS), 해시셋 풀이 다음 그래프에 대해 (1 2 3 4 5 6 7 8 9 10 11 12) 라는 방문 순서가 있다면 다음과 같이 판별할 수 있다. 시작 노드인 1이 3개의 인접 노드를 가지고 있으므로 다음 3개의 수(2~4번째)는 1의 인접 노드이어야한다. 그 다음 노드인 2가 2개의 인접 노드를 가지고 있으므로 다음 2개의 수(5~6번째)는 2의 인접 노드이어야한다. ... 모든 노드가 위 조건을 만족하면 올바른 순서임을 알 수 있다. 표로 나타내면 다음과 같다. 빨간색 숫자가 검사할 숫자 파란색 숫자가 그의 인접한 노드가 위치해야하는..

[백준] 16947. 서울 지하철 2호선 (Java)

문제 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 알고리즘 그래프, 깊이우선탐색(DFS), 너비우선탐색(BFS) 풀이 DFS를 통해 사이클(순환선)을 찾아 표시하고, BFS를 통해 사이클이 아닌 노드에서 사이클인 노드까지 최소 거리를 구해 문제를 해결하였다. 사이클 찾기 ( DFS ) 모든 역은 연결되어있으므로 임의의 한 역에서 출발하여 DFS로 모든 간선을 탐색한다. 이때 이미 방문한 노드를 다시 방문한다면 사이클이 있는 것이므로 해당 노드까지 다시 되돌아가며 그 사이 역들을 모..

[백준] 16948. 데스 나이트 (Java)

문제 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 알고리즘 그래프, 너비우선탐색(BFS) 풀이 기존 사방으로 탐색했던 BFS 과정을 문제에서 주어진 6 방향으로 바꾸기만 하면 되는 문제이다. 좌표와 이동 횟수를 큐에 삽입해 6 방향으로 탐색하며 (r2,c2)에 도달했다면 그때의 이동 횟수를 출력하고 도달하지 못하고 BFS 가 종료되었다면 -1 을 출력한다. * 큐에 삽입하므로 최소 이동 횟수가 적은 상태부터 탐색한다. 따라서 도달..

[백준] 1261. 알고스팟 (Java)

문제 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 알고리즘 0-1 너비우선탐색 (0-1 BFS) 풀이 벽이 없다면 가중치가 0이고, 벽이 있다면 가중치가 1인 0-1 BFS 문제이다. 가중치가 동일하지 않기 때문에 큐를 사용하면 N,M에 도착했을 때의 벽을 부순 횟수가 최솟값이라고 확신할 수 없다. 따라서 큐가 아닌 우선순위 큐를 이용하여 부순 횟수가 적은 순으로 정렬하고 탐색해 N, M에 도착했을 때 벽을 부순 횟수가 최솟값이 될 수 있도록 한다. * 우선순위 큐에서 꺼낼 때 N,M..

[백준] 14226. 이모티콘 (Java)

문제 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 알고리즘 너비우선탐색 (BFS) 풀이 이모티콘 복사, 붙여넣기, 하나 삭제 모두 1초가 걸리므로 BFS를 이용해 세 연산을 하며 S 개에 도달했을 때 시간을 출력한다. 하지만 화면에 있는 이모티콘 수가 같더라도, 클립보드에 복사된 이모티콘 수가 다를 수 있다. 따라서 큐에 현재 화면에 있는 이모티콘 수, 걸린 시간 뿐만 아니라 클립보드의 이모티콘 수도 저장해야하며 방문 체크를 위한 배열 또한 visited[화면에 있는 이모티콘 수][클립보드의 이모티콘 수] 형..

[백준] 13913. 숨바꼭질 4 (Java)

문제 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 알고리즘 너비우선탐색(BFS) 풀이 BFS 로 목적지까지의 최단 시간를 찾고, 그 경로를 역추적해야하는 문제이다. BFS를 통해 N부터 출발하여 +1, -1, *2 로 이동하면서 K까지의 최단 시간을 구한다. 이때 기존의 방문 처리를 위한 boolean형 배열 visited 대신 int형 배열 before을 사용하여 이전 위치를 저장하면 K에 도착했을 때 해당 배열의 값을 거슬러올라가는 것으로 경로를 역추적할 수 있다. 경로..

[백준] 1707. 이분 그래프 (Java)

문제 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 알고리즘 그래프, 이분 그래프, 너비우선탐색(BFS) 풀이 인접한 정점의 색이 칠해져있지 않다면 현재 정점의 색과 반대로 칠해가면서 인접한 정점과 현재 정점의 색이 같은 경우가 생긴다면 이분 그래프가 아니므로 NO를 출력한다. 정점의 개수가 최대 20,000개, 간선의 개수가 최대 200,000개이므로 O(V2) 의 시간, 공간 복잡도를 갖는 인접 행렬이 아닌 O(V+E)의 시간, 공간 복잡도를 갖는 인접 리스트를 사용한다. 각 정점의 색을 저장할 colo..

[프로그래머스] 거리두기 확인하기 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 너비우선탐색(BFS) 풀이 대기실마다 해당 대기실의 대해 모든 응시자를 큐에 넣고 거리 2까지 너비우선탐색을 진행해 다른 응시자까지 도달할 경우 거리두기를 지키지 않은 것이고, 어떤 다른 응시자에게도 도달할 수 없었다면 거리두기를 지킨 것이다. 1. places의 원소를 [강의실 번호][y][x]의 3차원 배열에 삽입하고 응시자의 좌표를 강의실 번호에 해당하는 큐에 삽입한다. 2. 각 강의실마다 거리 2까지 BFS를 진행해 다른 응시자에게 도달했다면 다음 강의실로 이동하고, 다음 강의실로 이동하..