CodeDrive

문제:

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1<=N<=1,000, 0<=M<=Nx(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1<=u,v<=N, u!=v) 같은 간선은 한 번만 주어진다.

출력:

첫째 줄에 연결 요소의 개수를 출력한다.

풀이방법:

인접리스트와 dfs를 사용해서 이 문제를 사용했다. N, M을 입력받은 뒤에 인접리스트 U를 초기화하고, visited 배열을 초기화 했다. 방문하지 않은 정점에 대해서만 dfs를 수행해서 연결 요소의 개수를 구했다. 

문제링크:

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

문제:

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

연구소는 크기가 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

문제:

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫재 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

입력:

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

출력:

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

풀이방법:

pypy3로 통과한 코드입니다. 0인 점에서 가능한 모든 경우의 수를 탐색하면서 백트래킹을 수행해 python3에서 통과하지 못한듯 합니다.

우선 sudoku 배열에 입력을 모두 받아준 뒤에 이를 순회하면서 0인 점을 찾아서 toDoList로 만들어 준다.

이를 인덱스로 접근하는 재귀 함수 check에 넣어주면서 백트래킹을 수행한다.

isPromising를 통해서 가능한 경우의 수를 구해주도록 했다. set 자료형과 차집합을 이용해서 경우의 수를 구하도록 했다. 이 경우의 수를 넣어보면서 dfs 방식으로 답을 구해주도록 한다.

인덱스가 끝까지 진행을 하면 sys.exit()로 바로 종료하도록 했다. (스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않으며, 여럿인 경우여도 하나만 출력하면 되기 때문이다.)

문제링크:

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

문제:

 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다.

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다.(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다.)

또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다.

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다.

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

입력:

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1 이상 100 이하의 정수이다.

출력:

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

풀이방법:

 bfs를 사용해서 풀수는 있을 것 같지만 dfs를 사용해서 풀었다. 재귀의 깊이가 얼마나 될지 모르고, deepcopy를 사용하기 위해서 sys와 copy를 import 했다.

 지역의 높이 정보 입력값을 받으면서 max 연산을 취해서 지역 내에 가장 높은 영역이 값을 얻도록 했다. (뒤에서 for 반복문에서 사용하기 위해) 입력을 다 받은 뒤에는 이 높이 정보를 deepcopy한 뒤 현재 rain에 맞게(1부터 시작한다.) 값을 빼주고 만약 0 이하로 떨어지게 된다면 0으로 만들고 나머지는 그대로 냅뒀다.

 이제 이렇게 비에 잠긴 영역들을 표시했으니 dfs를 사용해서 살아있는 영역의 개수를 구한다. 각 점을 탐색하며 0이 아닌 곳에서 dfs 탐색을 시작하며 탐색 되는 곳은 0으로 만들어줘서 방문했음을 알려준다. 이렇게 반복해서 하면 영역의 개수를 구할 수 있고 max 연산을 통해 최댓값을 구한다.

문제링크:

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

문제:

우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

입력:

사람들은 1, 2, 3, ..., n (1<=n<=100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘때 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.

각 사람의 부모는 최대 한 명만 주어진다.

출력:

입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이 때에는 -1을 출력해야 한다.

풀이방법:

두 사람이 얼마나 긴 간격으로 연결되어 있는지 확인하는 문제이기 때문에 dfs나 bfs로 풀어야 할 것 같다고 생각했다. dfs로도 풀 수 있는지 정확히 모르지만, 두 사람 사이의 몇 level(단계)가 있는지 확인하면 되는 문제 이므로 bfs를 사용하기로 했다.

형제들 같은 경우에는 2촌으로 계산되는데 그 이유가 (나에서 부모님으로 1촌) + (부모님에서 형제로 1촌) 이기 때문이다. 따라서 이러한 관계를 알기 위해서는 양방향으로 이동할 수 있도록 relation을 만들었고, 중복방문을 하지 않기 위해서 visited를 만들었다.

처음 시작해야 하는 사람의 번호로 시작한다. 그리고 그 사람과 관계가 있는 사람들 중 방문하지 않았던 사람만 temp라는 배열에 담고 방문한 것으로 visited를 변경한다. 그리고 이 temp에 나와의 관계가 알고 싶은 사람의 번호가 있는지 확인하고, 있다면 break 없다면 temp의 길이를 재서 탐색할 사람이 있는지 확인한다. temp에 더 탐색할 사람이 있다면 위의 행동을 다시 반복하고, 더 이상 탐색할 사람이 없다면 친척 관계가 전혀 없다는 것으로 출력하면 된다.

그리고 최종 출력에서 +1을 했는데, 이 이유는 temp에 내가 원하는 사람의 번호가 있기 때문에 그 관계로 이동한다는 행동이 빠져있었기 때문에 +1을 해서 출력하도록 했다.

문제링크:

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

문제:

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 NxN인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다.)

예를 들어, 그림이 아래와 같은 경우에

RRRBB

GGBBB

BBBRR

BBRRR

RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1)하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강, 초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다. (1<=N<=100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력:

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해서 출력한다.

풀이방법:

dfs를 사용해서 구역을 구분하는 문제인데, 적록색약인 사람과 그렇지 않은 사람을 구분하기 위해 각각 dfs 함수를 구현해 주면 된다. 그리고 또한 입력을 받을 때 G나 R을 R이나 G로 바꿔주어 적록색약인 사람들을 구분하면 된다. 이번 풀이에서는 G를 R로 바꾸었다.

문제링크:

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

문제:

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약은 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.

(한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다.)

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.

예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다.

(0은 배추가 심어져 있지 않는 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.)

입력:

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1<=M<=50)과 세로길이 N(1<=N<=50), 그리고 배추가 심어져 있는 위치의 개수 K(1<=K<=2500)이 주어진다. 그 다음 K줄에는 배추의 위치(0<=X<=M-1),Y(0<=Y<=N-1)가 주어진다.

출력:

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

풀이방법:

dfs를 전형적인 문제이다. 탐색을 진행하다가 1인 점을 만나게 되면(그리고 이전에 방문을 하지 않았다면) dfs 함수에 들어가서 주위에 있는 1의 위치들을 모두 방문하는 방식으로 진행하면 된다. 주위의 1을 모두 방문한 뒤에 answer를 1증가 시키며 다시 탐색을 진행하여 1이지만 방문을 안한 점을 찾아 같은 작업을 반복해주면 된다.

문제링크:

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

문제:

n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다.(-_-)

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 살 수 있는지 고민에 빠져 잇따. 우리의 임무는 이 사육사를 도와주는 것이다. n*n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 오래 살려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력:

첫째 줄에 대나무 숲의 크기 n(1<=n<=500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에는 판다가 최대한 살 수 있는 일수(K)를 출력한다.

풀이방법:

 기본적으로는 dfs를 사용해서 판다의 이동 경로를 알아야 하지만 문제에서 원하는 것은 판다가 최대한 살 수 있는 일수, 즉 최대로 이동 가능한 거리의 길이를 원하고 있다. 작은 크기의 경우에는 시작점을 달리 해서 최대 일수를 찾을 수 있지만 500 x 500의 경우에는 이 것을 다 탐색하기에는 많은 시간이 걸릴 것이다.

 따라서 이를 해결하기 위해서 다이나믹 프로그래밍에서 메모리제이션을 사용한다. 한 점에서 출발을 해서 움직이다가 이미 이전에 다른 곳에서 움직였던 기록이 남아있고 그것을 기록해뒀다면 더 이상 그 길로 이동할 필요없이 그 값을 참조해서 다시 돌아오면 된다. 따라서 dfs로 이동을 하지만 이전에 이 길을 지나간 기록이 있다면 그 값을 가져오고, 그렇지 않다면 더 들어가면서 값을 기록하도록 한다.

 또한 재귀적으로 함수를 구현했기 때문에 깊은 재귀로 인한 에러를 방지하기 위해서 sys.setrecursionlimit를 사용한다.

문제링크:

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

문제:

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계까 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다."를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력:

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

풀이방법:

bfs를 사용해서 이 문제를 풀었다. 이 문제에서는 신뢰 관계가 양방향으로 존재한다는 가정이 없기 때문에 신뢰 관계를 정리 할 때, 단방향으로만 해야 한다. 일반적인 리스트를 사용해도 상관이 없지만 python의 시간 초과를 해결하기 위해 deque를 사용하고자 하였다. 하지만 그래도 python으로는 시간초과가 발생하였고,(한 명도 python으로 통과한 사람이 아직 없다.)그래서 결국 pypy3으로 통과했다.

 그 외의 특이사항으로는 방문했는지 확인하는 배열인 conti가 존재한다는 것이다. 아직 방문하지 않는 컴퓨터일 때에만 값을 갱신하며 count가 증가하도록 했다.

문제링크:

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

문제:

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

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

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

입력:

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

출력:

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

풀이방법:

제일 많이 파고 들어가야 하는 문제이므로 DFS와 백트래킹을 사용하는 것이 적합하다. DFS를 사용해서 한 번 깊게 파고 난 뒤에 움직이지 못하는 경우가 된다면 다시 되돌아와서 다른 곳으로 깊게 파고 들어가도록 한다. 이때부터는 최대로 깊게 들어간 기록이 있으므로 이 기록을 넘길 때에만 값을 갱신하도록 하였다. 이렇게 모두 탐색을 마치고 더 이상 이동할 곳이 없다면 출력하도록 했다.

문제링크:

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