본문 바로가기

DFS, BFS 문제모음11

[알고리즘 BFS & DFS 20] CHOOSENUMBER 문제 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자. 1234567 3 1 1 5 5 4 6 이 경우에는 첫째 줄에서 1, 3, 5를 뽑는 것이 답이다. 첫째 줄의 1, 3, 5밑에는 각각 3, 1, 5가 있으며 두 집합은 일치한다. 이때 집합의 크기는 3이다. 만약 첫.. 2019. 8. 12.
[알고리즘 BFS & DFS 19] COWART 문제 소에 대해 잘 알려지지 않은 사실은 소들 눈에는 빨간색과 초록색이 같아보이는 적록색약이라는 것이다. 이 사실은 인간뿐만아니라 소에게도 호소력있는 예술 작품을 만들기 어렵게한다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에 copy RRRBB GGBBB BBBRR BBRRR RRRRR 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, .. 2019. 8. 12.
[알고리즘 BFS & DFS 17] DAM 문제 어느 마을 안에는 큰 호수가 있고, 그것을 막는 댐이 있었다. 그런데 어느날 그 댐이 무너져내려 호수에 있는 물이 마을을 모두 뒤덮으려한다. 호수에 있는 물은 다음 1시간에 한 블럭으로 이동하며, 물의 양은 무한하다 가정하자. 물은 상 하 좌 우로 퍼져나가며 마을을 뒤덮는다. 당신은 댐이 터진 순간 이 마을의 지도를 받았다. 당신이 도와줘야 할 일은 완공시간이 K시간인 댐들을 최대한 빨리 지어서 물이 더 이상 진행하지 못하도록 하는 것이다. 입력 첫 줄에는 배열의 크기인 T(1 ≤ T ≤100)가 주어지고 다음 줄부터 배열의 값이 주어진다. 0은 텅 빈 길, 1은 건물이다. (물은 건물을 뒤덮지 못한다고 가정한다.) 그리고 그 다음 줄에는 호수의 좌표 x, y(1 ≤ x, y ≤ T) 가 주어지고,.. 2019. 8. 12.
[알고리즘 BFS & DFS 15] ICEBERG 입력 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다. 출력 첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다. 예제 입력 5 7 0 0 0 0 0 0 0 0 2 4 5 3 0 0 0 3 0 2 5 2.. 2019. 8. 12.
[알고리즘 BFS & DFS 10] TEAMPROJECT 문제 이번 가을학기에 '문제 해결' 강의를 수강하는 학생들은 팀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 같은 팀의 팀원으로 구성된 한 팀도 허락된다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 같이하고 싶은 학생 딱 한 명을 선택해야 한다. 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 과목을 수강한 학생 수가 1명이고, 그 한 명이 자기 자신을 선택하는 경우. 혹은, 학생 수가 N명이고, 1번 학생이 2번 학생을 선택하고, 2번 학생이 3번 학생을 선택하고,..., N-1번 학생이 N번 학생을 선택하고, N번 학생이 1번 학생을 선택하는 경우에만 한 팀이 될 수 있다. 예를 들어, 수업에 7명의 학생이 있다고 하자. 학생들을 1.. 2019. 8. 12.
[알고리즘 BFS & DFS 9] LETTER 문제 세로 R칸, 가로 C칸으로 나누어진 표 모양의 판이 있다. 판의 각각의 모든 칸에는 대문자 알파벳이 하나씩 적혀 있다. 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 인접한 네 칸(상하좌우) 중의 한 칸으로 이동할 수 있다. 이때 매순간 여태 지나온 칸에 적힌 알파벳과 다른 알파벳 칸으로만 이동할 수 있다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 말이 가능한 많은 칸을 지나도록 할 때, 몇 칸을 이동할 수 있는지 구하는 프로그램을 작성하시오. 말이 지나는 칸은 초기에 말이 위치했던 칸도 포함된다. 입력 첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R, C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 C개의 대문자 알파벳들이 주어진다. 출력 첫째 줄에 말이 이동.. 2019. 8. 12.
[알고리즘 BFS & DFS 8] PRIMEPATH 문제 4자리 소수가 2개 주어질때, 시작 수에서 도착 수까지 아래에 주어지는 규칙에 맞게 변경할때 최소 변경 횟수를 구하는 프로그램을 작성해보자. 규칙은 어떤 수에서 다음 수로 넘어갈때 어떤 수의 한 자리수 만 변경해서 이동한다. 각 단계별 수는 소수이다. 만약 1033에서 8179로 가야한다면, 다음과 같은 순서로 이동하게되어 최소 변경 횟수는 6이된다. copy 1733, 3733, 3739, 3779, 8779, 8179 입력은 항상 네 자리 소수만(1000 이상의 소수) 주어진다고 가정하자. 주어진 두 소수는 ‘네 자리 수’라 하였기 때문에 0013 과 같은 1000 미만의 소수는 입력되지않는다. 입력 첫 줄에 소수 쌍의 수 T(1 ≤ T ≤ 100)가 주어진다. 다음 T줄에 걸쳐 각 줄에 시작 .. 2019. 8. 12.
[알고리즘 BFS & DFS 5] TREASURE 문제 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안된다. 예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다. 보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 .. 2019. 8. 12.
[알고리즘 BFS & DFS 4] TOMATO 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한.. 2019. 8. 12.
[알고리즘 BFS & DFS 2] CHEEZE 문제 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색 으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모칸에 엑스친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다. 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어 가게 된다. 의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후 에 녹아 없어져서 와 같이 된다. 다시 한 시간 후에는 에서 ‘c’로 표시된 부분이 녹아 없어져서 과 같이 된다. 은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남.. 2019. 8. 12.
[알고리즘 BFS & DFS 1] CONNECTEDCOMP 문제 정점의 번호가 1부터 N까지 존재하는 그래프 G가 존재하고, 어떠한 정점 집합 S={i, j, k,..} 끼리는 서로 간선으로 연결되어있으며, 그 이외의 정점 집합(S`)과는 연결되어있지 않을때, 집합 S로 그려지는 그래프를 그래프 G의 연결요소(Connected Component)라고 합니다. 만약 정점 집합 S와 S`의 합집합이 G의 정점의 전체일 경우, 그래프 G의 연결요소의 개수는 2개입니다. 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 V과 간선의 개수 E이 주어진다. (1 ≤ V ≤ 1,000, 0 ≤ E ≤ V×(N-1)/2) 둘째 줄부터 E개의 줄에 간선의 양 끝점 v1와 v2가.. 2019. 8. 12.

티스토리툴바