그래프탐색-DFS
-
JUNGOL/Intermediate_Coder/그래프탐색-DFS/3230 : 두 로봇코딩 테스트/JUNGOL 2022. 5. 20. 20:33
Intermediate_Coder/그래프탐색-DFS/두 로봇 문제 2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번방, 2번 방, …, N번 방으로 부른다. 통로는 정확히 N-1개가 발견되었는데, 각각 서로 다른 두 방 사이를 연결시켜주며 중간에 다른 통로와 이어지는 경우는 없다고 한다. 또한 이 통로들을 이용하여 임의의 두 방 사이를 이동하는것이 가능하며, 임의의 두 방 사이를 이동할 때 같은 통로를 두 번 이상 지나지 않는 경로는 유일한 것으로 밝혀졌다. 새로 발견된 동굴을 조사하기 위해 동굴 탐사 로봇 두 대를 이용하기로 하였다. 두 로봇은 어떤 시점이..
-
JUNGOL/Intermediate_Coder/그래프탐색-DFS/3428 : 등수 찾기(ranking)코딩 테스트/JUNGOL 2022. 1. 25. 11:24
Intermediate_Coder/그래프탐색-DFS/등수 찾기(ranking) 문제 KOI 본선 대회에 N명의 학생이 참가했다. 이 학생들을 각각 1부터 N까지 정수로 표현하자. 대회가 끝나고 성적을 발표하는데, 이 대회는 전체 학생의 등수를 발표하는 대신, 두 학생 A, B가 대회 본부에 찾아가면 본부는 두 학생 중 어느 학생이 더 잘 했는지를 알려준다. 둘 이상의 학생이 동점인 경우는 없다. 자신의 전체에서 등수가 궁금한 학생들은 둘 씩 짝을 지어서 대회 본부에 총 M번 질문을 했다. 여러분은 등수를 알고 싶은 학생 X와 대회 본부의 질문에 대한 답들로부터, 이 학생 X의 등수 범위를 찾아서 출력한다. 물론 이 학생의 등수는 1등, 즉 전체에서 제일 잘한 경우부터 N등, 즉 전체에서 제일 못한 경우..
-
JUNGOL/Intermediate_Coder/그래프탐색-DFS/2462 : 키 순서코딩 테스트/JUNGOL 2022. 1. 20. 16:51
Intermediate_Coder/그래프탐색-DFS/키 순서 문제 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자. 1번 학생의 키 < 5번 학생의 키 3번 학생의 키 < 4번 학생의 키 5번 학생의 키 < 4번 학생의 키 4번 학생의 키 < 2번 학생의 키 4번 학생의 키 < 6번 학생의 키 5번 학생의 키 < 2번 학생의 키 이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 ..
-
JUNGOL/Intermediate_Coder/그래프탐색-DFS/1912 : 미로 탐색코딩 테스트/JUNGOL 2022. 1. 6. 17:58
Intermediate_Coder/그래프탐색-DFS/미로 탐색 문제 동현이는 방이 N개인 미로의 지도를 갖고 있다. 각 방에는 1번부터 N번까지 번호가 매겨져 있고, N개의 방 사이에는 M개의 문이 있으며, 각 문은 서로 다른 두 방을 연결한다. 동현이는 1번 방에서 출발해서 N개의 방을 모두 탐색해 볼 것이다. 동현이는 모험심이 강하기 때문에 항상 새로운 방을 찾기를 원한다. 동현이는 자신이 위치한 방과 연결된 방 중 한 번도 들르지 않은 방이 있다면 그 중 가장 번호가 작은 방으로 가고, 그렇지 않으면(연결된 방이 모두 전에 들렀던 방이면) 그냥 왔던 곳으로 되돌아가게 된다. 동현이가 N개의 방을 모두 방문하고 1번 방으로 오면 동현이는 탐색을 끝낸다. N개의 방을, 동현이가 먼저 방문한 순으로 정렬..
-
JUNGOL/Intermediate_Coder/그래프탐색-DFS/1840 : 치즈코딩 테스트/JUNGOL 2021. 12. 28. 15:32
Intermediate_Coder/그래프탐색-DFS/치즈 문제 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모칸에 엑스친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다. 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어 가게 된다. 의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후 에 녹아 없어져서 와 같이 된다. 다시 한 시간 후에는 에서 ‘c’로 표시된 부분이 녹아 없어져서 과 같이 된다. ..
-
JUNGOL/Intermediate_Coder/그래프탐색-DFS/1457 : 영역 구하기코딩 테스트/JUNGOL 2021. 12. 15. 20:27
Intermediate_Coder/그래프탐색-DFS/영역 구하기 문제 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다. 와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다. M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그..
-
JUNGOL/Intermediate_Coder/그래프탐색-DFS/1695 : 단지번호붙이기코딩 테스트/JUNGOL 2021. 12. 10. 19:16
Intermediate_Coder/그래프탐색-DFS/단지번호붙이기 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 형식 첫 번째 줄에는 지도의 크기 N(정사각형임으로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1..