본문 바로가기

그래프

[BOJ] 백준 20530번 양분 (Java)
Dot Algo∙ DS/PS 2022. 2. 26. [BOJ] 백준 20530번 양분 (Java) #20530 양분 난이도 : 골드 2 유형 : 트리 / DFS 20530번: 양분 첫째 줄에 두 자연수 $N$, $Q$가 주어진다. 주어지는 그래프의 정점과 간선의 개수가 $N$개이며 쿼리가 $Q$개 주어진다는 것을 의미한다. 둘째 줄부터 $N$개의 줄에는 $i$번 간선이 연결하는 두 정점 www.acmicpc.net ▸ 문제 나무 T는 양분을 먹고 자란다. 원래 나무는 정점 N개와 간선 N−1개로 구성되어야 하지만, 양분을 너무 많이 먹어버린 나머지 나무 T는 N개의 간선을 갖게 되었다. 더 이상 트리가 아니기 때문에 T는 꿈의 무대인 트리와 쿼리에 등장하지 못한다. 슬퍼하고 있는 T 위해 정휘는 새로운 문제를 만들어 주었다. N개의 정점과 N개의 간선으로 이루어진 연결 그래프 T가 주어진다. 정점은 ..
[BOJ] 백준 1865번 웜홀 (Java)
Dot Algo∙ DS/PS 2021. 12. 21. [BOJ] 백준 1865번 웜홀 (Java) #1865 웜홀 난이도 : 골드 3 유형 : 그래프 탐색 / 벨만포드 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net ▸ 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다..
[BOJ] 백준 1926번 그림 (Java)
Dot Algo∙ DS/PS 2021. 10. 16. [BOJ] 백준 1926번 그림 (Java) #1926 그림 난이도 : 실버 1 유형 : 그래프 / BFS 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net ▸ 문제 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다. ▸ 입력 첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(..
[BOJ] 백준 6593번 상범 빌딩 (Java)
Dot Algo∙ DS/PS 2021. 10. 15. [BOJ] 백준 6593번 상범 빌딩 (Java) #6593 상범 빌딩 난이도 : 골드 5 유형 : 그래프 / BFS 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net ▸ 문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리..
[BOJ] 백준 13023번 ABCDE (Java)
Dot Algo∙ DS/PS 2021. 10. 14. [BOJ] 백준 13023번 ABCDE (Java) #13023 ABCDE 난이도 : 골드 5 유형 : 그래프 / DFS 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net ▸ 문제 BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다. 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다. A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오. ▸ 입력 첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진..
[BOJ] 백준 2458번 키 순서 (Java)
Dot Algo∙ DS/PS 2021. 10. 11. [BOJ] 백준 2458번 키 순서 (Java) #2458 키 순서 난이도 : 골드 4 유형 : 그래프 이론 / 플로이드 와샬 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net ▸ 문제 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자. 1번 학생의 키 < 5번 학생의 키 3번 학생의 키 < 4번 학생의 키 5번 학생의 키 < 4번 학생의 키 4번 학생의 키 < ..
[프로그래머스] 2020 카카오 #3 자물쇠와 열쇠 (Java)
Dot Algo∙ DS/PS 2021. 9. 5. [프로그래머스] 2020 카카오 #3 자물쇠와 열쇠 (Java) #3 자물쇠와 열쇠 난이도 : LEVEL3 유형 : 그래프, 시뮬레이션 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr ▸ 문제 고고학자인 "튜브"는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다. 잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어..
[프로그래머스] 2019 카카오 블라인드 #7 블록 게임 (Java)
Dot Algo∙ DS/PS 2021. 9. 1. [프로그래머스] 2019 카카오 블라인드 #7 블록 게임 (Java) #7 블록 게임 난이도 : LEVEL4 유형 : 그래프 / 시뮬레이션 코딩테스트 연습 - 블록 게임 [[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,4,0,0,0],[0,0,0,0,0,4,4,0,0,0],[0,0,0,0,3,0,4,0,0,0],[0,0,0,2,3,0,0,0,5,5],[1,2,2,2,3,3,0,0,0,5],[1,1,1,0,0,0,0,0,0,5]] 2 programmers.co.kr ▸ 문제 프렌즈 블록이라는 신규 게임이 출시되었고, 어마어마한 상금이 걸린 이벤트 대회가 개최 되었다. 이 대회는 사람을 대신해서 플레이할 프로그램으로 참가해도 된다는 규정이 있어..

티스토리툴바

티스토리툴바