CodeDrive

문제:

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력:

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력:

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

풀이방법:

dfs를 사용해서 이 문제를 풀 수 있다. dfs는 다음과 같이 구성되어 있다.

1. 한 점으로부터 시작해 상하좌우를 탐색한다. (처음은 1행 1열)

2. 상하좌우를 탐색할 때, 아직 방문하지 않았고, 처음보는 알파벳이라면 그 방향으로 다시 dfs를 탐색한다.

3. dfs를 시작하는 순간마다. 현재까지 가지고 있는 알파벳 수를 기억해서 최대 몇칸을 지날 수 있는지 확인한다.

4. 더 이상 이동하지 못하는 경우에 한 dfs를 빠져나오게 되며, 방문 기록과 알파벳 탐색 기록을 지운다.

최종적으로 3번을 통해 기록한 값을 출력하면 된다.

문제링크:

https://www.acmicpc.net/problem/1987

문제:

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력:

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

풀이방법:

 bfs를 사용하여 각 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역들의 넓이를 구한다. 전체 영역을 1로 초기화하고 직사각형의 꼭짓점을 입력값으로 받을 때, 내부 영역들을 0으로 재정의한다.

 이 과정을 모두 마친 뒤, (0,0)부터 bfs를 사용하여 분리된 영역들의 각 넓이를 구한다. 한 점으로부터 시작해 이동하면서 visited를 업데이트하여 중복적으로 이동하는 것을 막으며 더 이상 이동하지 못할 때, 하나의 분리된 영역의 넓이를 구한 것으로 파악한다.

 탐색하는 과정을 region이 1이고, 방문하지 않은(visited가 0인) 곳에 대해 반복적으로 BFS를 수행하고, 이 결과들을 출력한다.

문제링크:

https://www.acmicpc.net/problem/2583

문제:

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 

입력:

첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.

다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

출력:

첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.

풀이방법:

 이 문제의 핵심은 물과 고슴도치의 이동을 BFS로 확인하면서 고슴도치가 비버의 집까지 갈 때까지 물의 영향을 받지 않는 지 확인해야 한다.

 우선 물에 대해서 BFS를 수행하면서 한 번 퍼질 때마다 1씩 늘어나면서 visit 배열이 채워진다. 이 때, 벽이나 비버의 집에는 물이 차지 않도록 한다.

 그 다음에는 고슴도치의 이동에 대해서 BFS를 수행하며 배열 안에 존재하며 비버의 집을 찾을 때 종료되도록 한다. 고슴도치가 이동할 때에는 물이 퍼진 정도에 따라 이동을 할 수 있으며, 물의 visit 배열 값보다 작을 때에만 이동할 수 있다. (물의 값이 4, 고슴도치가 이동할 값이 5라면 이동 불가 -> 물이 이미 차 있기 때문)

문제링크:

www.acmicpc.net/problem/3055

문제:

예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는 프로그램을 개발을 하였지만 어디로 낙하해야 자신의 수색 범위 내에서 가장 많은 아이템을 얻을 수 있는지 알 수 없었다.

각 지역은 일정한 길이 l (1 ≤ l ≤ 15)의 길로 다른 지역과 연결되어 있고 이 길은 양방향 통행이 가능하다. 예은이는 낙하한 지역을 중심으로 거리가 수색 범위 m (1 ≤ m ≤ 15) 이내의 모든 지역의 아이템을 습득 가능하다고 할 때, 예은이가 얻을 수 있는 아이템의 최대 개수를 알려주자.

주어진 필드가 위의 그림과 같고, 예은이의 수색범위가 4라고 하자. ( 원 밖의 숫자는 지역 번호, 안의 숫자는 아이템 수, 선 위의 숫자는 거리를 의미한다) 예은이가 2번 지역에 떨어지게 되면 1번,2번(자기 지역), 3번, 5번 지역에 도달할 수 있다. (4번 지역의 경우 가는 거리가 3 + 5 = 8 > 4(수색범위) 이므로 4번 지역의 아이템을 얻을 수 없다.) 이렇게 되면 예은이는 23개의 아이템을 얻을 수 있고, 이는 위의 필드에서 예은이가 얻을 수 있는 아이템의 최대 개수이다.

입력:

첫째 줄에는 지역의 개수 n (1 ≤ n ≤ 100)과 예은이의 수색범위 m (1 ≤ m ≤ 15), 길의 개수 r (1 ≤ r ≤ 100)이 주어진다.

둘째 줄에는 n개의 숫자가 차례대로  각 구역에 있는 아이템의 수 t (1 ≤ t ≤ 30)를 알려준다.

세 번째 줄부터 r+2번째 줄 까지 길 양 끝에 존재하는 지역의 번호 a, b, 그리고 길의 길이 l (1 ≤ l ≤ 15)가 주어진다.

출력:

예은이가 얻을 수 있는 최대 아이템 개수를 출력한다.

풀이방법:

플로이드-와샬 알고리즘을 적용해서 이 문제를 풀 수 있다. 플로이드-와샬 알고리즘은 주어진 그래프의 경로로 가중치를 초기화한 후 i에서 j로 가는 경로에 k가 추가 되었을 때, 이전의 경로의 가중치보다 작아지는지 확인하면 된다. 

플로이드-와샬로 초기화를 완료한 뒤에, 지역의 개수 n을 반복문으로 순회한다. 순회하면서 임계점에 해당하는 값인 m보다 작은 값들을 모두 더해주고, 마지막에 현재 시작한 지역의 값을 더해주도록 한다. 이 중 가장 큰 값을 출력하도록 한다.

문제링크:

www.acmicpc.net/problem/14938

문제:

도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)

그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.

입력:

첫째 줄에 컴퓨터의 수 N (1 ≤ N ≤ 1000)가 주어진다.

둘째 줄에는 연결할 수 있는 선의 수 M (1 ≤ M ≤ 100,000)가 주어진다.

셋째 줄부터 M+2번째 줄까지 총 M개의 줄에 각 컴퓨터를 연결하는데 드는 비용이 주어진다. 이 비용의 정보는 세 개의 정수로 주어지는데, 만약에 a b c 가 주어져 있다고 하면 a컴퓨터와 b컴퓨터를 연결하는데 비용이 c (1 ≤ c ≤ 10,000) 만큼 든다는 것을 의미한다. a와 b는 같을 수도 있다.

출력:

모든 컴퓨터를 연결하는데 필요한 최소비용을 첫째 줄에 출력한다.

풀이방법:

 이러한 문제는 최소 스패닝 트리를 사용해서 푸는 전형적인 문제다. Kruskal, Prim 알고리즘으로 풀 수 있으며, 이번 문제는 Prim 알고리즘을 활용해서 풀었다.

 Prim 알고리즘은 다음의 순서대로 작동한다.

1. 그래프에서 하나의 꼭짓점을 선택하여 트리를 만든다.
2. 그래프의 모든 변이 들어 있는 집합을 만든다.
3. 모든 꼭짓점이 트리에 포함되어 있지 않은 동안
   1. 트리의 연결된 변 가운데 트리 속의 두 꼭짓점을 연결하지 않는 가장 가중치가 작은 변을 트리에 추가한다.

 이 알고리즘이 종료되었을 때 만들어진 트리는 최소 비용 신장 트리가 된다. [출처: Prim 알고리즘 위키피디아]

따라서 위 알고리즘대로 해당 노드로 이동하는 최소 비용을 의미하는 distance 배열을 INF로, 전체 가중치를 가지고 있는 vertice를 초기화 하고, 모든 컴퓨터를 방문했는지 확인할 수 있는 visited 배열을 만든다.

 이제 1번 컴퓨터(인덱스상 0번)를 임의로 선택하여 위 알고리즘대로 트리를 만들기 시작한다. 1번 컴퓨터로 향하는 distance는 0이다. (문제 조건 상 a와 b가 같을 수 있다고 하는데 큰 의미는 없는 것 같다.) distance와 visited 배열을 바탕으로 선택해야 하는 distance를 고른다.( 첫번쨰의 경우에는 당연히 1번 컴퓨터만 distance가 변경되었으므로 1번 컴퓨터다.) 1번 컴퓨터가 선택되었으므로, 이 컴퓨터와 연결 된 Edge들을 distance에 반영한다.

 위 과정을 모든 컴퓨터를 다 방문할 때까지 반복하며, 알고리즘이 종료되었을 때의 distance의 합이 최소 비용을 의미하게 된다.

문제링크:

www.acmicpc.net/problem/1922

문제:

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력:

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

출력:

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

풀이방법:

 위키피디아에 따르면 이분 그래프란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다. 즉 한 변의 양 끝은 빨강과 파랑으로 서로 달라야 한다는 것이다.

 dfs로 정점을 탐색하며, visited에다 색을 기록한다. dfs로 탐색하는 도중에 visited에 서로 다른 색이 들어오게 되면 이분그래프가 아니므로 False를 반환하도록 한다.

문제링크:

www.acmicpc.net/problem/1707

문제:

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력:

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력:

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

풀이방법:

너비 우선 탐색의 가장 기초적인 문제다. 이미 지나온 곳을 다시 방문하지 않도록 0으로 초기화된 visited 배열을 만들었고, 현재 stage에서 나이트가 있을 수 있는 위치를 able이라는 배열에 저장하도록 했다. 

bfs 함수 내에선 우선 able 내에 목적지가 있는지 확인하는 과정을 먼저 거친다. 있다면 현재 stage(count)를 출력하도록 하고, 없으면 나이트가 움직일 수 있는 경우의 수인 candidate를 able을 각 케이스에 대해 더해줘서 새로운 able을 만들도록 한다. 이 과정을 재귀적으로 반복하면서 값을 찾는다.

문제링크:

www.acmicpc.net/problem/7562

문제:

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 상근이의 동기의 수 n(2<=n<=500)이 주어진다. 둘째 줄에는 리스트의 길이 m(1<=m<=10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai,bi가 주어진다. (1<=ai<bi<=n) ai와 bi가 친구라는 뜻이며, bi 와 ai도 친구관계이다.

출력:

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

풀이방법:

우선 입력으로 받은 값들을 그래프 형식으로 정리를 하는 작업을 거친다. 이후 BFS 방식을 사용해서 level이 2까지 가는 친구들(친구의 친구)을 찾는다. 항상 시작은 1이므로 queue에 1을 넣고 BFS 탐색을 두번 한다. 그렇게 탐색을 마치고 1을 제거한 뒤에 배열의 길이를 출력하도록 한다.

문제링크:

https://www.acmicpc.net/problem/5567

문제:

풀이 방법:

<Test 32 시간초과>

 <2021.07.11 수정>

DFS와 같이 재귀적인 방법을 사용하는 것이 시간을 많이 소요할 것 같아 일반적으로 그래프에서 최소 거리를 구하는 방법으로 많이 사용되는 다익스트라 방법을 사용했다. 1에서 부터의 거리를 측정하기 때문에, 1에서 다익스트라로 거리를 구한 뒤에 K보다 작은 것의 갯수를 세서 반환하도록 한다.

문제 링크:

https://programmers.co.kr/learn/courses/30/lessons/12978

문제:

풀이 방법:

문제 링크: