본문 바로가기

BFS

[BOJ] 백준 16920번 확장 게임 (Java)
Dot Algo∙ DS/PS 2022. 3. 19. [BOJ] 백준 16920번 확장 게임 (Java) #16920 확장 게임 난이도 : 골드 2 유형 : 그래프 탐색 / BFS 16920번: 확장 게임 구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위 www.acmicpc.net ▸ 문제 구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위에 있다. 한 칸 위에 성이 두 개 이상인 경우는 없다. 게임은 라운드로 이루어져 있고, 각 라운드마다 플레이어는 자기 턴이 돌아올 때마다 성을 확장해야 한다. 제일 먼저 플레이어 1이 확장..
[BOJ] 백준 9177번 단어 섞기 (Java)
Dot Algo∙ DS/PS 2022. 3. 11. [BOJ] 백준 9177번 단어 섞기 (Java) #9177 단어 섞기 난이도 : 골드 4 유형 : 문자열 / bfs 9177번: 단어 섞기 세 개의 단어가 주어졌을때, 꿍은 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 궁금해졌다. 첫 번째와 두 번째 단어는 마음대로 섞어도 되지만 원래의 순서는 섞여서는 www.acmicpc.net ▸ 문제 세 개의 단어가 주어졌을때, 꿍은 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 궁금해졌다. 첫 번째와 두 번째 단어는 마음대로 섞어도 되지만 원래의 순서는 섞여서는 안 된다. 다음과 같은 경우를 생각해보자. 첫 번째 단어 : cat 두 번째 단어 : tree 세 번째 단어 : tcraete 보면 알 수 있듯이, 첫 번째 단어와 두 번째 단어를 서로 섞어서 세 번째..
[BOJ] 백준 1726번 로봇 (Java)
Dot Algo∙ DS/PS 2022. 3. 6. [BOJ] 백준 1726번 로봇 (Java) #1726 로봇 난이도 : 골드 3 유형 : 그래프 탐색 / BFS 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net ▸ 문제 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다. 명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다. 명령 2. Turn dir: dir은 left 또는 right 이며, 각..
[BOJ] 백준 19581번 두 번째 트리의 지름 (Java)
Dot Algo∙ DS/PS 2022. 2. 28. [BOJ] 백준 19581번 두 번째 트리의 지름 (Java) #19581 두 번째 트리의 지름 난이도 : 골드 1 유형 : 트리 / BFS 19581번: 두 번째 트리의 지름 트리에 N개의 정점이 있고, 각 정점 별로 1부터 N까지의 번호가 붙어있다. 트리에서 가장 먼 두 정점 간의 거리를 트리의 지름이라고 한다. 트리의 지름을 구하는 문제는 너무 많기 때문에 우리 www.acmicpc.net ▸ 문제 트리에 N개의 정점이 있고, 각 정점 별로 1부터 N까지의 번호가 붙어있다. 트리에서 가장 먼 두 정점 간의 거리를 트리의 지름이라고 한다. 트리의 지름을 구하는 문제는 너무 많기 때문에 우리는 두 번째 트리의 지름을 구하려고 한다. 두 번째 트리의 지름은 무엇이냐? 바로 두 번째로 가장 먼 두 정점 간의 거리를 의미한다. (두 번째 트리의 지름은 트리의 지름과 같..
[BOJ] 백준 2842번 집배원 한상덕 (Java)
Dot Algo∙ DS/PS 2022. 2. 6. [BOJ] 백준 2842번 집배원 한상덕 (Java) #2842 집배원 한상덕 난이도 : 플레 5 유형 : 투 포인터/ BFS 2842번: 집배원 한상덕 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 www.acmicpc.net ▸ 문제 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 지역의 고도도 알고 있다. 매일 아침 상덕이는 마을의 모든 집에 우편을 배달해야 한다. 배달은 마을에 하나밖에 없는 우체국 'P'가 있는 곳에서 시작한다. ..
[BOJ] 백준 2132번 나무 위의 벌레 (Java)
Dot Algo∙ DS/PS 2021. 12. 17. [BOJ] 백준 2132번 나무 위의 벌레 (Java) #2132 나무 위의 벌레 난이도 : 골드 3 유형 : 트리 / BFS / DFS 2132번: 나무 위의 벌레 첫째 줄에는 트리의 정점의 개수를 나타내는 정수 n(1 ≤ n ≤ 10,000)이 주어진다. 다음 줄에는 차례로 1번, 2번, …, n번 정점에 매달려 있는 열매의 개수가 주어진다. 다음 n-1개의 줄에는 트리의 각 www.acmicpc.net ▸ 문제 전산학(Computer science)에서 트리란 사이클이 없는 그래프를 말한다. 트리(Tree)라는 이름이 의미하듯, 이러한 구조는 나무의 모습에서 유래한다. 즉, 트리의 각 간선(edge)들이 나무의 가지를 나타내고, 각 정점(node)들은 가지가 갈라지는 지점을 의미한다. 또한 트리의 루트는 나무의 뿌리를 의미한다. 이러한 구조는 일반적인 ..
[BOJ] 백준 4179번 불! (Java)
Dot Algo∙ DS/PS 2021. 12. 15. [BOJ] 백준 4179번 불! (Java) #4179 불! 난이도 : 골드 4 유형 : 그래프 탐색 / BFS 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net ▸ 문제 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다. 지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다. 불은 각 지점에서 네 방향으로 확산된다. 지훈이는 미로의 ..
[BOJ] 백준 3197번 백조의 호수 (Java)
Dot Algo∙ DS/PS 2021. 11. 30. [BOJ] 백준 3197번 백조의 호수 (Java) #3197 백조의 호수 난이도 : 플레 5 유형 : 그래프 탐색 / BFS 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net ▸ 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다..

티스토리툴바

티스토리툴바