CodeDrive

문제:

<그림1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림2>는 <그림1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력:

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5<=N<=25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0 혹은 1)가 입력된다.

출력:

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

풀이방법:

 이 문제는 크게 두 부분으로 나누어서 풀어야 한다. check에 <그림2>와 같이 배열을 만드는 부분, 그리고 <그림2>를 탐색하며 각 단지번호의 갯수를 세는 부분으로 나누어서 풀었다.

 첫 부분은 dfs를 사용해서 값을 할당했다. <그림1>의 배열을 탐색하면서 값이 1이고 check가 아직 0인(방문을 하지 않은) 값을 만나면 그 값으로부터 dfs를 시작하도록 한다. check에 count 값을 할당하면서 다음 dfs 값으로 이동하였다. 이 때 상하좌우로 이동할 수 있었는데 깔끔하게 이동할 수 있도록 dx와 dy라는 배열을 만들어서 하나의 반복문으로 이동을 간단하게 만들었다.

 이렇게 한 단지를 다 탐색하고 나면 다시 처음상태로 돌아가서 다시 값이 1이고 check가 0인 곳을 찾고, 위와 동일하게 check에 count에 1이 증가한 값들을 할당해주면 된다.

 <그림1>을 모두 탐색하고 난다면 check에 <그림2>와 같이 지도를 얻을 수 있다. 그러면 이 check를 count의 갯수만큼 탐색하며 단지번호의 갯수를 세도록 한다.

문제링크:

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

문제:

다음과 같이 정의된 수열이 있다.

• D[1] = A
• D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합

예를 들어 A=57, P=2일 때, 수열 D는 {57, 74(=5^2+7^2=25+49),65,61,37,58,89,145,42,20,4,16,37, ...}이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다.

이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 {57,74,65,61}의 네 개의 수가 남게 된다.

입력:

첫째 줄에 A(1<=A<=9999),P(1<=P<=5)가 주어진다.

출력:

첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다.

풀이방법:

 DFS를 사용해서 풀어야 하는 문제이다. check라는 배열을 250000이라고 설정하고(최대 나올 수 있는 값은 9^5+9^5+9^5+9^5 이기 때문이다.) dfs로 하나씩 들어가면서 해당하는 값에 count를 할당한다. 이렇게 계속해서 값을 구하다가 check가 0이 아닌 값을 만난다면 그 값부터는 반복된다는 뜻이므로 그 check의 count에 1을 뺀 값이 정답이 되게 된다.

 이 문제로 예시를 들면 check[57]에 count를 1을 할당. ->check[74]에 2를 할당 -> check[65]에 3을 할당 -> check[61]에 4를 할당 -> check[37]에 5를 할당 -> check[58]에 6을 할당 -> check[89]에 7을 할당 -> check[145]에 8을 할당 -> check[42]에 9를 할당 -> check[20]에 10을 할당 -> check[4]에 11을 할당 -> check[16]에 12를 할당 -> check[37]에는 이미 5가 할당되어 있음. 따라서 57, 74, 65, 61만 남아야 하므로 답은 5-1인 4가 된다.

문제링크:

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

문제:

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열(3,2,7,8,1,4,5,6)을 배열을 이용해 표현하면 다음과 같다. 

또는 Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

순열을 배열을 이용해 [그림1] 과 같이 나타냈다면, 임의의 노드 i에서 다른 노드 p로 간선을 이어 그래프로 만들 수 있다.

Figure 1에 나와있는 것 처럼, 순열 그래프(3,2,7,8,1,4,5,6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클"이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N(2<=N<=1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

출력:

각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.

풀이방법:

 DFS를 사용해서 풀 수 있는 문제이다. 1번 노드부터 시작해서 노드를 방문할 때마다 check를 1로 바꾼다. check가 1인 노드를 만나면 dfs를 종료하고 answer를 하나 증가시켜 순열 사이클의 개수를 나타내도록 하였다. 

 처음에는 DFS 함수를 재귀적으로 구현하고 제출했는데 런타임 에러가 발생하게 되었다. 코드를 봐도 런타임 에러가 발생할만한 곳이 없었는데 찾아보니 자체 시스템 상으로 재귀의 최대 한도가 정해져 있는데 이를 넘어가면 런타임 에러가 발생한다고 한다. 따라서 이 한도를 수정해야하는데 sys 모듈에 sys.setrecursionlimit() 라는 함수를 사용하면 재귀의 깊이 한도(?)를 조절 할 수 있다고 한다. 따라서 이 값을 2000으로 설정하고 코드를 다시 제출해 보았는데 통과할 수 있었다.

문제링크:

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

문제:

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

체스판의 가로 세로의 길이 n이 매개변수로 주어질 때 , n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution 함수를 완성해주세요.

풀이 방법:

 되추적 방법을 사용하는 대표적인 예시인 문제이다. 따라서 queens에서는 각 col별로 queen을 배치하는데 우선 promising이라는 함수에서 이전에 배치한 col을 기준으로 해당 인덱스에 queen을 배치할 수 있는지 판단해준다. 모든 방법을 다 판별해주는 방법도 생각할 수 있지만 그럴 경우 n이 커짐에 따라 많은 시간이 발생할 것이다. 따라서 promising이라는 되추적 판단을 해주는 함수로 인해서 많은 시간을 단축 할 수 있었다.

문제 링크:

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

문제:

케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람의 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?

천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Backjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.

케빈 베이컨은 미국 헐리우드 영화배우들끼리 케빈 베이컨 게임을 했을 때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.

오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 적은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.

1은 2까지 3을 토해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+1+2 = 6 이다.

2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다.

3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4를 통해 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 1+1+1+2 =5 이다.

4는 1까지 1단계, 2까지 3을 통해 2단계, 3까지 1단계, 5까지 1단계 만에 알 수 있다. 4의 케빈 베이컨의 수는 1+2+1+1 = 5가 된다.

마지막으로 5는 1까지 4를 통해 2단계, 2까지 4와 3을 통해 3단계, 3까지 4를 통해 2단계, 4까지 1단계 만에 알 수 있다. 5의 케빈 베이컨의 수는 2+3+2+1 = 8이다.

5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다.

BOJ 유저의 수와 친구 관계 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 유저의 수 N(2<=N<=100)과 친구 관계의 수 M(1<=M<=5,000)이 주어진다. 둘째 줄부터 M

개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다.

출력:

첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 적은 사람을 출력한다. 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다.

풀이방법:

일단 모든 사람들에 대해서 케빈 베이컨의 수를 계산해야 하므로 BFS로 값을 탐색해야 한다고 생각했다.  for를 사용한 반복문은 입력값을 정리하기 위한 반복문이다. (보통 저는 bfs, dfs는 이와 같이 입력값들을 정리합니다.) answer는 각 사람 별로 count의 값을 담아주는 배열이고, 인덱스를 편리하기 관리하기 위해 1번 사람이 1번째 인덱스를 가지도록 하였다. person은 인덱스 값으로 교체해줘도 괜찮을 것 같지만 bfs 내에서 한 단계 이상 넘어간다면 여러 개의 값을 가져야 할 것 같아서 애초에 배열 값으로 넣게 되었다. 그리고 또한 자기 자신의 값을 탐색하지 않도록 자신의 값은 -1로 초기화 한 상태로 값을 넣었다.

문제링크:

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

문제:

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력:

첫째 줄에 자연수 N과 M이 주어진다. (1<= M <= N < 8)

출력:

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이 방법:

재귀적인 방법으로 길이가 M이 될 때까지 계속해서 넣어준다. 대신 이 문제에서는 중복을 허용하지 않았기 때문에 이에 대한 조건도 있어야 하고 증가하는 순서로 출력해야 하므로 배열에 들어있는 끝 값보다 클 때만 넣어줘야 한다는 조건 역시 필요하다. 이 문제에 대한 시리즈가 여러개 있는데 이에 맞는 조건을 넣어주면 된다.

문제 링크:

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

문제:

풀이 방법:

<Test 32 시간초과>

 <2021.07.11 수정>

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

문제 링크:

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

문제:

입력:

출력:

풀이 방법:

문제:

입력:

출력:

풀이 방법:

문제 설명:

문제 풀이:

먼저 표의 현황을 깔끔하게 정리를 하기 위해서 tickets을 반복문으로 돌아가면서 이를 딕셔너리 타입(해시) 방식으로 정렬을 하였다. 매번 추가하면서 정렬을 한 이유는 만약 가능한 경로가 여러개라면 알파벳 순서가 앞서는 경로를 우선으로 해야하기 때문이다.

티켓을 정리한 뒤에 재귀적으로 탐색을 하는 함수인 travel에 ticket의 정보를 담고 있는 answer_set, 실제 경로인 answer, 출발하는 공항의 이름인 start, 그리고 모든 항공권을 사용했는지 탐색해야하므로 티켓의 갯수인 K 와 몇 개를 사용했는지 알려주는 count를 사용하였다.

처음에는 무조건 ICN에서 시작을 한다는 조건이 있었으므로 초기값은 ICN으로 시작한다. travel 함수에는 세 가지 조건이 존재한다. 

1. count == K 일 때

종료 조건으로 모든 티켓을 다 사용한 경우에 해당한다. 따라서 True를 반환한다.

2. 잘못 경로를 탐색해서 들어갔을 경우

해시 구조를 통해서 티켓을 정리했다보니 B 공항으로 도착을 하긴 했지만 B 공항에서 출발을 하는 티켓이 없을 수도 있다. 따라서 이 경우에 이 값을 찾으려 하면 error가 발생하기 때문에 예외처리구문을 사용해서 이 case를 탐지했다. 이 경우가 발생한거면 잘못된 경로를 온 것이기 때문에 answer의 마지막 값을 빼주고 잘못된 경로이므로 False를 반환한다.

3. 위 두 경우가 아닐 때

해시로 정리한 티켓을 기준으로 하나씩 경로를 늘려가면서 탐색해본다. 

위 과정을 거치다보면 answer를 구할 수 있게 된다.