CodeDrive

문제:

인터넷 방송 KOI(Korea Open Internet)의 음악 프로그램 PD인 남일이는 자기가 맡은 프로그램 '뮤직 KOI'에서 가수의 출연 순서를 정하는 일을 매우 골치 아파한다. 순서를 정하기 위해서는 많은 조건을 따져야 한다.

그래서 오늘 출연 예정인 여섯 팀의 가수에 대해서 남일이가 보조 PD 세 명에게 각자 담당한 가수의 출연 순서를 정해오게 하였다. 보조 PD들이 가져온 것은 아래와 같다.

• 1 4 3
• 6 2 5 4
• 2 3

첫 번째 보조 PD는 1번 가수가 먼저, 다음에 4번 가수, 다음에 3번 가수가 출연하기로 순서를 정했다. 두 번째 보조 PD는 6번, 2번, 5번, 4번 순으로 자기 담당 가수들의 순서를 정했다. 한 가수를 여러 보조 PD가 담당할 수도 있다. 마지막으로, 세 번째 보조 PD는 2번 먼저, 다음에 3번으로 정했다.

남일이가 할 일은 이 순서들을 모아서 전체 가수의 순서를 정하는 것이다. 남일이는 잠시 생각을 하더니 6 2 1 5 4 3으로 순서를 정했다. 이렇게 가수 순서를 정하면 세 보조 PD가 정해온 순서를 모두 만족한다. 물론, 1 6 2 5 4 3으로 전체 순서를 정해도 괜찮다.

경우에 따라서 남일이가 모두를 만족하는 순서를 정하는 것이 불가능할 수도 있다. 예를 들어, 세 번째 보조 PD가 순서를 2 3 대신에 3 2로 정해오면 남일이가 전체 순서를 정하는 것이 불가능하다. 이번에 남일이는 우리 나라의 월드컵 4강 진출 기념 음악제의 PD를 맡게 되었는데, 출연 가수가 아주 많다. 이제 여러분이 해야 할 일은 보조 PD들이 가져 온 순서들을 보고 남일이가 가수 출연 순서를 정할 수 있도록 도와 주는 일이다.

보조 PD들이 만든 순서들이 입력으로 주어질 때, 전체 가수의 순서를 정하는 프로그램을 작성하시오.

입력:

첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 가수의 수가 나오고, 그 뒤로는 그 가수들의 순서가 나온다. N은 1이상 1,000이하의 정수이고, M은 1이상 100이하의 정수이다.

출력:

출력은 N 개의 줄로 이뤄지며, 한 줄에 하나의 번호를 출력한 다. 이들은 남일이가 정한 가수들의 출연 순서를 나타낸다. 답이 여럿일 경우에는 아무거나 하나를 출력 한다. 만약 남일이가 순서를 정하는 것이 불가능할 경우에는 첫째 줄에 0을 출력한다.

풀이방법:

 순서가 정해져있는 작업을 차례로 수행해야 할 때 순서를 결정해주는 문제이므로 '위상 정렬'을 사용해야 한다. 위상 정렬에 대한 설명은 다음 페이지에 설명이 잘 되어 있기에 링크를 달아두도록 한다.

https://m.blog.naver.com/ndb796/221236874984

 문제의 설명에서 '세 번째 보조 PD가 순서를 2 3 대신에 3 2로 정해오면 남일이가 전체 순서를 정하는 것이 불가능하다.' 라는 것이 있는데, 이는 위상 정렬을 수행할 때 사이클이 생기는 경우에 해당한다. 이러한 경우에 위상정렬을 하면서 순서를 정할 때, N명이 모두 순서가 정해지지 않게 된다.

 따라서 위상정렬을 하고 난 뒤에 길이가 N이 아니라면 -1을 출력하도록 한다.

문제링크:

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

문제:

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다.

출력:

첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

풀이방법:

X인 부분을 그리디하게 채워나가도록 한다. X가 4개이상이라면 AAAA로 채우고, 4개 미만이라면 BB로 채우도록 한다. 이 때, X가 남은 경우 혹은 X가 부족한 경우가 덮을 수 없는 케이스라고 판단한다.

문제링크:

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

문제:

NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.

시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.

시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과 열의 위치를 의미하며, 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당한다.

예를 들어 다음과 같이 3x3 크기의 시험관이 있다고 하자. 서로 다른 1번, 2번, 3번 바이러스가 각각 (1,1), (1,3), (3,1)에 위치해 있다. 이 때 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류를 계산해보자.

1초가 지난 후에 시험관의 상태는 다음과 같다.

2초가 지난 후에 시험관의 상태는 다음과 같다.

결과적으로 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류는 3번 바이러스다. 따라서 3을 출력하면 정답이다.

입력:

첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분되어 주어진다. 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어진다. 또한 모든 바이러스의 번호는 K이하의 자연수로만 주어진다. N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)

출력:

S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력한다. 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.

풀이방법:

 바이러스 번호가 낮은 것부터 2차원 배열에 확산시키는 문제로 너비 우선 탐색에 해당한다. 처음에는 시간을 고려하지 않고, 너비 우선 탐색만 생각하고 문제를 풀려고 했으나 계속해서 시간초과가 발생하게 되었다.

 처음 생각했던 방법은 중복으로 탐색하는 경우도 많았으며, 이미 다 채워져 있었는데 시간(S)이 남았다는 이유로 계속 2차원 배열 탐색을 계속했기 때문에 시간초과가 발생했던 것으로 보인다. 

 그래서 deque에 바이러스 종류, 시간, 좌표등을 모두 저장하고 이를 기준으로 바이러스를 증식시키는 것으로 수정하게 되었다. 초기 시험관을 받고 바이러스 정보를 모두 deque에 넣고 정렬하면 낮은 종류의 바이러스부터 먼저 증식시킬 수 있다.

문제링크:

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

문제:

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.

어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. i는 0부터 시작한다.

출력:

첫째 줄에 줄을 선 순서대로 키를 출력한다.

풀이방법:

 이 문제는 그리디하게 채워나가는 것을 목표로 한다. 우선 N과 같은 길이의 0으로 채워진 배열(answers)을 생성한 후 다음과 같은 조건으로 채워나간다.

1. 현재 answers 인덱스에 이미 사람이 채워져 있는가?
2. 만약 비어있다면, 내가 들어갈 차례인가?
   1. 비어있던(answers가 0) 횟수가 내 순서와 같은가?

 즉, answers가 0인 경우에 자기보다 큰 사람이 들어갈 자리라고 생각하며, 이 자리를 미리 고려하면서 빈 자리에 들어가는 것을 선택한다.

문제링크:

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

문제:

시골에 있는 태양이의 삼촌 댁에는 커다란 참외밭이 있다. 문득 태양이는 이 밭에서 자라는 참외가 도대체 몇 개나 되는지 궁금해졌다. 어떻게 알아낼 수 있는지 골똘히 생각하다가 드디어 좋은 아이디어가 떠올랐다. 유레카! 1m2의 넓이에 자라는 참외 개수를 헤아린 다음, 참외밭의 넓이를 구하면 비례식을 이용하여 참외의 총개수를 구할 수 있다.

1m2의 넓이에 자라는 참외의 개수는 헤아렸고, 이제 참외밭의 넓이만 구하면 된다. 참외밭은 ㄱ-자 모양이거나 ㄱ-자를 90도, 180도, 270도 회전한 모양(┏, ┗, ┛ 모양)의 육각형이다. 다행히도 밭의 경계(육각형의 변)는 모두 동서 방향이거나 남북 방향이었다. 밭의 한 모퉁이에서 출발하여 밭의 둘레를 돌면서 밭경계 길이를 모두 측정하였다.

예를 들어 참외밭이 위 그림과 같은 모양이라고 하자. 그림에서 오른쪽은 동쪽, 왼쪽은 서쪽, 아래쪽은 남쪽, 위쪽은 북쪽이다. 이 그림의 왼쪽위 꼭짓점에서 출발하여, 반시계방향으로 남쪽으로 30m, 동쪽으로 60m, 남쪽으로 20m, 동쪽으로 100m, 북쪽으로 50m, 서쪽으로 160m 이동하면 다시 출발점으로 되돌아가게 된다.

위 그림의 참외밭  면적은 6800m2이다. 만약 1m2의 넓이에 자라는 참외의 개수가 7이라면, 이 밭에서 자라는 참외의 개수는 47600으로 계산된다.

1m2의 넓이에 자라는 참외의 개수와, 참외밭을 이루는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나는 변의 방향과 길이가 순서대로 주어진다. 이 참외밭에서 자라는 참외의 수를 구하는 프로그램을 작성하시오.

입력:

첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나는 변의 방향과 길이 (1 이상 500 이하의 정수) 가 둘째 줄부터 일곱 번째 줄까지 한 줄에 하나씩 순서대로 주어진다. 변의 방향에서 동쪽은 1, 서쪽은 2, 남쪽은 3, 북쪽은 4로 나타낸다.

출력:

첫째 줄에 입력으로 주어진 밭에서 자라는 참외의 수를 출력한다.

풀이방법:

 참외밭의 모양은 ㄱ-자 이거나 해당 모양의 회전 형태로 구성되어 있다. 이러한 모양의 넓이는 구하는 방법은 아래 그림을 참고하면 쉽게 구할 수 있다.

 이 문제에서 원하는 넓이는 노란색 영역의 넓이다. 해당 넓이를 (노랑+빨강) 직사각형에서 빨강의 직사각형을 빼는 방식으로 쉽게 구할 수 있다. 따라서 이 문제에서 해야할 것은 가장 긴 가로 길이와 가장 긴 세로 길이를 구하고, 이를 통해 작은 직사각형의 넓이를 구하는 것이다.

 입력으로 주어진 방향과 길이 배열을 한번씩 순회하면서 가장 긴 가로, 세로 길이를 구하고 배열의 인덱스를 저장한다. 그러면 가장 긴 가로, 세로 인덱스를 기준으로 양 옆의 길이 차를 계산하면 작은 직사각형의 가로 및 세로 길이를 구할 수 있게 된다.

 최종적으로 큰 직사각형과 작은 직사각형의 가로, 세로 길이를 모두 알 수 있게 되었으므로 이 둘의 차를 구한 뒤 K 값을 곱해주도록 한다.

문제링크:

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

문제:

2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다.

진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다.

하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다.

꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다. 꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다.

꽃을 심을 때는 주의할 점이있다. 어떤 씨앗이 꽃이 핀 뒤 다른 꽃잎(혹은 꽃술)과 닿게 될 경우 두 꽃 모두 죽어버린다. 또 화단 밖으로 꽃잎이 나가게 된다면 그 꽃은 죽어버리고 만다.

그림(c)는 세 꽃이 정상적으로 핀 모양이고 그림(d)는 두 꽃이 죽어버린 모양이다.

하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다.

단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다.

돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자!

입력:

입력의 첫째 줄에 화단의 한 변의 길이 N(6≤N≤10)이 들어온다.

이후 N개의 줄에 N개씩 화단의 지점당 가격(0≤G≤200)이 주어진다.

출력:

꽃을 심기 위한 최소 비용을 출력한다.

풀이방법:

화단의 한 변의 길이가 가장 큰 경우는 10이며, 꽃은 3개를 심을 수 있다. 이 때 양 끝 라인들은 꽃을 심을 경우 화단 밖으로 꽃잎이 나가게 되므로, 심지 못하는 구간이다. 따라서 8x8의 점에서 3개를 선택하는 것과 같다. 많지 않은 케이스를 가지고 있으므로, 모든 경우의 수를 구하고, 가능한지 여부를 파악한다. 그래서 가능한 경우에 비용만을 체크하여 최소 비용을 찾는다.

 따라서 combination을 사용하여 모든 케이스를 확인하고, 각 케이스에 대해 한 번의 BFS를 수행하여 겹치는 점이 있는지 확인하도록 한다. 겹치면 다음 케이스로 넘어가고, 없다면 최소비용을 업데이트하도록 한다.

 모든 케이스를 확인하고, 비용을 출력하도록 한다.

문제링크:

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

문제:

주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다.

‘쿵... 쿵...’

주난이는 점프의 파동으로 주변의 모든 친구들을 쓰러뜨리고(?) 누군가 훔쳐간 초코바를 찾으려고 한다. 주난이는 N×M크기의 학교 교실 어딘가에서 뛰기 시작했다. 주난이의 파동은 상하좌우 4방향으로 친구들을 쓰러뜨릴(?) 때 까지 계속해서 퍼져나간다. 다르게 표현해서, 한 번의 점프는 한 겹의 친구들을 쓰러뜨린다. 다음의 예를 보자.

1 # 1 0 1 1 1
1 1 0 1 0 0 1
0 0 1 * 1 1 1
1 1 0 1 1 1 1
0 0 1 1 0 0 1

주난이를 뜻하는 *은 (3, 4)에 있고, 초코바를 가진 학생 #는 (1, 2)에 있다. 0은 장애물이 없는 빈 공간임을 뜻하고, 1은 친구들이 서있음을 의미한다. 다음은 주난이의 점프에 따른 생존(?) 학생들의 변화이다.

1 # 1 0 1 1 1
1 1 0 0 0 0 1
0 0 0 * 0 1 1
1 1 0 0 1 1 1
0 0 1 1 0 0 1

1 # 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 * 0 0 1
0 0 0 0 0 1 1
0 0 0 0 0 0 1

0 X 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 * 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0

위의 예시에서 주난이는 3번의 점프 만에 초코바를 훔쳐간 범인을 찾아낼 수 있다!

주난이를 빨리 멈춰야 교실의 안녕을 도모할 수 있다. 주난이에게 최소 점프 횟수를 알려줘서 교실을 지키자.

입력:

첫째 줄에 주난이가 위치한 교실의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 300)

둘째 줄에 주난이의 위치 x1, y1과 범인의 위치 x2, y2가 주어진다. (1 ≤ x1, x2 ≤ N, 1 ≤ y1, y2 ≤ M)

이후 N×M 크기의 교실 정보가 주어진다. 0은 빈 공간, 1은 친구, *는 주난, #는 범인을 뜻한다.

출력:

주난이가 범인을 잡기 위해 최소 몇 번의 점프를 해야 하는지 출력한다.

풀이방법:

 한 번의 점프가 한 겹의 친구들을 쓰러뜨리고, 친구들을 쓰러뜨릴(?) 때 까지 반복한다는 것은 BFS를 반복적으로 사용한다는 것과 같다. 따라서 시작점으로부터 상하좌우로 BFS를 수행하도록 한다.

 여기서 한 번의 점프가 단순히 한번 상하좌우로 움직이는 것이 아니라 상하좌우로 모두 친구들을 쓰러뜨리는 것이다. 따라서 BFS를 탐색할 때, 친구가 있거나 초코바가 있다면 queue의 우측에 값을 넣도록 하고(다음 점프임을 의미), 그렇지 않다면 queue의 왼쪽에 값을 넣도록 한다(같은 점프 내에 쓰러져야함). visited 개념을 distance로 사용하여 몇 번째 점프인지 기록하도록 한다.

 이렇게 모든 점프를 마친 뒤에 초코바 위치에 있는 distance를 출력하도록 한다.

문제링크:

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

문제:

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력:

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력:

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

풀이방법:

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

2022.08.09 - [Algorithm/Python] - [BOJ]12851. 숨바꼭질 2

 이전 문제의 발전된 버전으로 가장 빠른 시간과 그 시간으로 이동한 경로를 출력해야 하는 문제다. 위 문제 해결 방법에 추가적으로 visited 배열을 이전에는 0과 1의 여부로만 사용했지만 count 값을 저장하도록 하여 최소 시간을 측정할 수 있도록 했다. 그리고 path라는 배열을 사용해서 이동한 점의 위치에 기존에 있었던 점의 값을 저장하도록 하여, 동생이 위치한 점에 도달했을 때, 역추론이 가능하도록 한다.

 역추론을 하기 위한 print_path라는 함수가 존재하며 history를 만든 후 이를 뒤집어서 출력하도록 한다.

문제링크:

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

문제:

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

입력:

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력:

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

풀이방법:

BFS를 사용하여 수빈이가 이동할 수 있는 거리내에서 동생이 있는 위치에 도달하는 시간을 측정하도록 한다.

수빈이가 이동할 수 있는 방법은 총 3가지이므로, 이동할 점이 가능한 범위 내에 존재하고 이전에 도달한 적이 없는 곳이라면 queue에 넣고 이동하도록 한다. 그러다 동생이 있는 위치에 도달하면 해당 시간의 count를 하나 증가 시키고, 모든 탐색을 마친 뒤에는 시간, count의 dict에서 최소 시간의 count를 출력하도록 한다.

문제링크:

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

문제:

한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.

      cdef  ...f  ..ef  ..gh  cdeh  cdej  ...f 
      bT..  .T.e  .Td.  .Tfe  bTfg  bTfi  .Tde 
      a...  abcd  abc.  abcd  a...  a.gh  abc. 
거리 :  6     6     6     8     8    10    6

위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.

입력:

첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다.

출력:

첫 줄에 거리가 K인 가짓수를 출력한다.

풀이방법:

 DFS를 사용해서 시작점에서 도착점까지 이동하고, 한 번의 이동마다 거리를 하나씩 늘린다. 도착점에 도달한 경우 거리가 K와 같다면 answer를 하나 증가시키고, 그렇지 않다면 다시 되돌아 오는 과정을 수행한다. '다시 되돌아 온다' 라는 행동을 하기 위해 visited 배열을 사용하고, 그 위치로 이동한 경우에는 해당 좌표의 값을 1로 바꾸고, 다시 되돌아 온 경우에는 0으로 다시 바꿔주도록 한다.

문제링크:

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