2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 접근한 방법 7576. 토마토 문제와 살짝 비슷합니다. 내부, 외부 공간을 굳이 구분할 필요는 없고 매 시간마다 처음 (0, 0) 좌표에서만 bfs를 수행하면서 치즈를 만나는 경우만 체크하여 제거 리스트에 올려주고 그 외 공간은 모두 탐색을 계속 진행하면 됩니다. 치즈를 만나는 경우는 탐색 대상에 들어가지 않기 때문에 애초에 치즈로 둘러쌓인 공간을 탐색할 일이 없습니다. 1. 전체 치즈 수를 체크합니다. 2. 좌표 0, 0 에서 bfs를 실행합니다. 상하좌우를 확인하여 공기만 경우..

2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 접근한 방법 비교적 풀이법이 단순한 완전탐색 문제. 지도가 몇 개의 육지로 나뉘어져 있는 지는 아무 상관 없습니다. L에 해당하는 모든 칸을 확인하여 BFS를 수행합니다. 1. L이면 BFS를 들어갑니다. 2. 시작점을 1로 잡고 이후 상하좌우로 방문하는 L칸 마다 +1씩 더하여 값을 넣어줍니다. (방문 처리) 3. 마지막으로 방문한 칸에서 시작점인 1을 뺀 값이 해당 좌표에서 계산된 시작점에서 가장 먼 지점까지의 거리가 됩니다. 4. 모든 L칸에 대해서 1~3 과..

2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 접근한 방식 1. 입력으로 n, m을 받고, 2차원 배열 arr에 빙산 정보를 저장합니다. 2. 주어진 4방향(dist)을 이용하여 빙산이 한 덩어리로 얼마나 오래 지속되는지 계산하는 solution 함수를 정의합니다. 3. dfs를 정의하고 모든 빙산이 연결되어 있는지 확인합니다. 4. solution 함수에서는 빙산이 1개로 이루어져 있거나 빙산이 나뉘어 있는 경우까지 계속 반복하여 빙산을 녹이고, 빙산이 1개로 이루어져 있을 때까지 걸리는 시간을 반환..

2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 접근한 방법 입력받은 용액들을 오름차순 정렬한 후 투 포인터로 해결할 수 있습니다. 포인터를 각각 배열의 왼쪽, 오른쪽 부분에서 시작하도록 설정하고 두 포인터가 엇갈리지 않을 때까지 포인터가 가리키는 각 배열의 값의 합의 최솟값을 갱신합니다. 값을 갱신할 때는 0에 수렴하는 값을 넣어줘야 하므로 절댓값으로 바꿔 넣어줍니다. 현재 순회중인 각 포인터가 가리키는 배열의 합이 0보다 큰 경우 오른쪽(큰 값)값을 줄여줘야 하므로 오른쪽..

9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 접근한 방식 입력받은 문자열을 각각 A와 B라고 한다면 크기가 (A의 길이 +1) * (B의 길이+1)인 2차원 DP 테이블 d를 만듭니다. d[i][j]를 계산하기 위해 다음 점화식을 사용합니다 a[i-1]과 b[j-1]이 같은 글자라면 d[i][j] = d[i-1][j-1] + 1을 넣어줍니다. LCS에 값을 추가할 수 있다는 것을 의미합니다. a[i-1]과 b[j-1]이 다르다면 d[i][j] = max(d[i..

10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 접근한 방법 적록색약인 배열의 R값을 모두 G, 혹은 G값을 모두 R로 바꿔준 후 적록색약이 아닌 배열과 동일하게 탐색을 넣어줍니다. 모든 값에 대하여 방문이 가능한 경우에만 결괏값을 +1카운트한 후 DFS로 상하좌우를 확인해 진입 시작값과 같은 값들을 모두 방문처리 해줍니다. 2번 탐색을 하고나면 적록색약이 아닌 경우와 적록색약인 경우의 결괏값을 얻을 수 있습니다. Python import sys sys.setrecursionlimit(4000) inpu..