CodeDrive

문제:

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

• “이제 슬슬 비번 바꿀 때도 됐잖아”
• “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
• “그럼 8179로 해”
• “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
• “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
• “귀찮아”

그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

입력:

첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.

출력:

각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.

풀이방법:

 소수를 찾기 위한 에라토스테네스의 체와 그리고 한 소수로부터 다른 소수로 이동하기 위한 bfs를 사용하는 문제다.

우선 네 자리 수인 모든 소수를 찾기 위해서 에라토스테네스의 체를 사용한다. 에라토스테네스의 체를 1부터 10000까지 적용을 한 뒤에 filter를 사용해 1000보다 큰 수들만 남기도록 한다.

 네 자리 소수를 모두 구한 뒤에는 bfs를 사용해서 기준이 되는 숫자와 네 자리 소수를 모두 비교해서 하나만 다른 경우에만 새 queue에 넣는 방식으로 진행한다. 이 때 중복 방문을 피하기 위해서 visited 배열을 사용한다. 만약 목적지 소수를 발견하면 bfs를 종료하고 answer를 출력하며, 만약 모든 소수를 방문해도 도달하지 못했다면 Impossible을 출력하게 한다.

문제링크:

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

문제:

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력:

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

풀이방법:

 3중 배열을 사용하거나 2중 배열 2개를 사용하는 bfs 문제다. 대부분의 bfs 문제들은 방문 여부를 기록하는 2중 배열을 사용하는데, 이 문제에서는 도중에 한 개의 벽을 부수고 이동할 수 있다는 점 때문에 3중 배열을 사용하도록 한다. 3중 배열 중 앞 두 값은 일반적인 좌표 탐색을 위해 사용되고, 맨 마지막 값은 broken으로써 0과 1만을 가지는 값으로 사용한다. 즉, broken이 처음에는 0으로 진행하다가, 부술 수 있다면 broken이 1로 이동하여 시간 손실 없이 bfs를 계속해서 진행할 수 있도록 한다.

 visited에다가 한 step씩 진행하면서 거리를 기록하며, 최종적으로 목표하는 점의 broken의 0과 1을 모두 탐색하도록 한다. 만약 두 값 모두 있다면 둘 중 작은 값으로, 하나만 있다면 그 값을 출력하고 없다면 -1을 출력하면 된다.

문제링크:

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

문제:

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.

예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.

보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 가로, 세로의 크기는 각각 50이하이다.

출력:

첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다.

풀이방법:

for(bfs) 방법을 사용해야 하는 방법으로 시간이 많이 필요한 문제라 생각했고, pypy3으로 통과했다. 지도의 모든 L에 대해서 bfs를 수행한다. 각 bfs에서는 해당 L로부터 가장 멀리 갈 수 있는 거리를 찾는다.

문제링크:

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

문제:

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력:

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

풀이방법:

**이 문제는 pypy3으로 통과했습니다.**

 이 문제는 for(bfs)라고 생각했다. 우선 bfs를 사용한 이유는 한 나라로부터 인접한 국가들을 찾는 방법은 bfs가 가장 적당하다고 생각했기 때문이다. 하지만 이러한 bfs를 NxN 크기의 땅에 모두에 대해서 수행해야 했기 때문에 for(bfs)라고 생각했다. 그리고 이러한 문제때문에 시간초과가 발생할 수 있을 것 같다는 걱정이 들었는데, 실제로 python3으로는 시간초과가 발생하여서 pypy3으로 이 문제를 해결하였다.

 bfs를 통해서 국경이 열리는 나라들을 찾으며 인구 수를 더하며 count를 센다. 한 번의 bfs 탐색이 끝나게 되면, 업데이트를 하는 과정을 거치고, 다시 이어서 bfs를 수행하도록 한다. 

 이러한 과정을 인구 이동이 발생하지 않을 때까지 반복한다.

문제링크:

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

문제:

눈금의 간격이 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

문제:

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (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

문제:

인체에 치명적인 바이러스르 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 NxM인 직사각형으로 나타낼 수 있으며, 직사각형은 1x1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3<=N,M<=8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력:

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

풀이방법:

벽을 3개 세우는 방법을 한 눈에 찾는 것은 어렵기 때문에 가능한 모든 경우의 수에 대해 벽을 세워보면서 안전 영역 크기가 최대인 경우를 찾아야 한다. 

input을 모두 받은 뒤에 지도를 한번 탐색해서 0인 점인 빈 칸과, 2인 바이러스가 담겨 있는 배열을 만든다. 그리고 itertools의 combinations를 사용해서 지도에서 빈 칸을 3개를 고르는 모든 경우의 수를 구하고, 0인 점의 배열의 길이를 safeArea라고 정의한다.(안전 영역 계산을 빠르게 하기 위함이다.)

combinations의 각 경우에 대해서 bfs(spreadVirus)를 수행한다. 처음 바이러스가 담겨 있는 배열을 queue로 생각하며 이를 하나씩 빼면서 상하좌우로 이동하는 것으로 생각하며, 바이러스가 이동했다면 이를 다시 배열에 담아서 이 배열의 크기가 0이 될 때까지 반복하도록 했다. 그리고 이 때마다 spreadCount를 하나씩 증가하면서 처음 0인 칸에서 얼마나 바이러스가 펴졌는지 체크하도록 한다.

그리고 최종적으로는 safeArea-spreadCount-3으로 안전영역의 크기를 구한다.(-3은 0에다가 벽을 3개 세웠기 때문이다.)

이렇게 모든 경우의 수에 대해 탐색을 하면서 maxVal을 업데이트해 최댓값을 구하도록 한다.

문제링크:

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

문제:

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬으 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다.

지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력:

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력:

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

풀이방법:

visited 배열과 bfs를 이용해서 섬의 개수를 세도록 한다.

우선 visited 배열을 만들고, 이를 countLand라는 함수에게 넘겨준다. countLand에서는 주어진 지도를 반복문으로 반복하면서 방문하지 않은 땅이라면 bfs 함수로 들어갈 수 있도록 하며, 이 때마다 count를 하나씩 늘려주는 역할을 한다.

bfs는 일반적인 bfs 함수와 동일하고, 다른점이 있다면 이 문제에서는 대각선까지도 이동이 가능하기 때문에 더 많은 상황을 고려해 줘야 한다.

문제링크:

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