배극곰의 IT식량창고

문제링크

https://leetcode.com/problems/pacific-atlantic-water-flow/description/

문제설명

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Example 1:

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0,4]: [0,4] -> Pacific Ocean 
       [0,4] -> Atlantic Ocean
[1,3]: [1,3] -> [0,3] -> Pacific Ocean 
       [1,3] -> [1,4] -> Atlantic Ocean
[1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean 
       [1,4] -> Atlantic Ocean
[2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean 
       [2,2] -> [2,3] -> [2,4] -> Atlantic Ocean
[3,0]: [3,0] -> Pacific Ocean 
       [3,0] -> [4,0] -> Atlantic Ocean
[3,1]: [3,1] -> [3,0] -> Pacific Ocean 
       [3,1] -> [4,1] -> Atlantic Ocean
[4,0]: [4,0] -> Pacific Ocean 
       [4,0] -> Atlantic Ocean
Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.

Example 2:

Input: heights = [[1]]
Output: [[0,0]]
Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.

Constraints:

• m == heights.length
• n == heights[r].length
• 1 <= m, n <= 200
• 0 <= heights[r][c] <= 105

문제풀이

처음엔 여타 그래프 탐색 문제를 풀듯이 인접행렬로 BFS 돌려서 조건에 맞게 좌표를 산출하면 되겠거니 하는 안일한 생각이었다.

하지만 이중for문으로 모든 좌표에서 BFS를 시행하는 것이 과연 맞는 전략일까 라는 의문이 들었고,

또 우측, 하측에 있는 Atlantic 바다와 좌, 상측에 있는 Pacific 바다로

모두 흐르는 좌표를 체킹하는 접근법이 떠오르지 않아서 레퍼런스를 참고했다.

그 결과 다시 세운 핵심전략은,

1. 시작좌표를 각 바다와 인접한 좌표들로만 배열을 구성한다. (Pacific, Atlantic 나눠서)
2. 파이썬의 set() 을 사용
    - Pacific으로 흐를 수 있는 좌표들의 set(),  Atlantic으로 흐를 수 있는 좌표들의 set() 을 따로 구하기.
        => 따로 BFS시행해야겠지
    - BFS 내에서도 visited라는 set()을 활용. 바다와 인접한 스타트 좌표들을 전부삽입.
        그리고 BFS를 통해 조건에 부합하여 큐에 삽입될때마다(방문할 때마다) 삽입  
3. 구한 집합들의 교집합을 구하면 된다. (set문법 활용)

리트코드는 다른 알고리즘 플랫폼들과 달리 이렇게 본인이 푼 솔루션의 시간복잡도, 공간복잡도 랭킹(?)도 알 수 있다.

코드

from collections import deque

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        d = [(0, 1), (0, -1), (1, 0), (-1, 0)]    #동, 서 남, 북
        m = len(heights)
        n = len(heights[0])
        pacific = set()		# pacific 바다로 흐를 수 있는 좌표들 집합
        atlantic = set()	# atlantic 으로 흐를 수 있는 좌표들 집합

        def bfs(starts):
            queue = deque(starts)
            visited = set(starts)

            while queue:
                curX, curY = queue.popleft()
                for dx, dy in d:
                    nx = curX + dx
                    ny = curY + dy

                    # 육지내에 속하고, 방문하지 않았고, 이전 셀의 높이보다 높아야함.
                    if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in visited and heights[nx][ny] >= heights[curX][curY]:
                        queue.append((nx, ny))
                        visited.add((nx, ny))
            
            return visited

        # 각 바다와 인접한부분의 좌표를 각 바다의 스타트 배열로 만든다.
        pStart = [(0, i) for i in range(n)] + [(i, 0) for i in range(1, m)]
        aStart = [(m-1, i) for i in range(n)] + [(i, n-1) for i in range(m-1)]

        pacific = bfs(pStart)
        atlantic = bfs(aStart)
    
        return list(pacific & atlantic) # 교집합 구해서 리스트 변환.
        # 핵심 아이디어: BFS
    
        # for문 돌려서 각지점에서 BFS 전부 시행??
        # 아틀란틱 => 우, 하 / 패시픽 -> 좌, 상 인데 체크조건을 어떻게 잡아야할까??

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/42577?language=python3

문제설명

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항
phone_book의 길이는 1 이상 1,000,000 이하입니다.
각 전화번호의 길이는 1 이상 20 이하입니다.
같은 전화번호가 중복해서 들어있지 않습니다.

문제풀이

 나의 아이디어
 번호의 길이가 다른데, 짧은번호가 배열의 앞에와야 유리한데..
 0번째 인덱스값과 그 나머지값을 비교하는 방식으로 늘려나가면서 검사?

 1. 배열을 받아서 각 문자열 값을 숫자로 변환한후 오름차순 정렬

변환하는 과정중에 

for item in arr:

   item = int(item) 으로 하니 배열값이 갱신이 안되어

for i in range()를 사용했다.

근데 나중에보니 오름차순 정렬을 문자열 상태일 때 해도 된다는걸 잊고있었다....

결국 정렬 후 감이 잘 안와서, 해시테이블을 쓰기로 했다.

구현할 로직

1. 폰북 배열 속 원소를 key로 하는 myDict 키,값 생성.
2. 폰북 속을 탐색하며 item 마다 각 item의 문자를 부분문자열로 하는 부분문자열 생성.
3. 그리고 그 부분 문자열이 myDict의 key로 속해있는지 검사
4. + 자기자신이 아닌지 검사
5. 조건문 하나라도 충족하면 False값 반환

코드

def solution(phone_book):
    answer = True
    myDict =  {}
    
    for item in phone_book:
        myDict[item] = 1

    for item in phone_book:
        part = ""
        for num in item:
            part += num # 문자를 더해가며 부분문자열 생성
            if part in myDict and part != item:
                return False
    # 1. 폰북 배열 속 원소를 key로 하는 myDict 키,값 생성.
    # 2. 폰북 속을 탐색하며 item 마다 각 item의 문자를 부분문자열로 하는 부분문자열 생성.
    # 3. 그리고 그 부분 문자열이 myDict의 key로 속해있는지 검사
    # 4. 자기자신이 아닌지 검사
    # 5. 조건문 하나라도 충족하면 False값 반환
    return answer

문제링크

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

문제설명

9 8
CCTGGATTG
2 0 1 1

0

4 2
GATA
1 0 0 1

2

문제풀이

핵심

- 문자열에서 특정 조건을 만족하는 크기가 고정된 부분 문자열을 탐색하기 위해 슬라이딩 윈도우 활용

- 딕셔너리를 사용하여 각 필요한 알파벳 충족개수를 비교하는 로직에 활용하였다.

시간복잡도를 줄이기 위해 활용하는 슬라이딩 윈도우의 본질을 잊지말자!

(이중반복문 X)

반복문 작성시에는 항상 인덱스를 초과하지 않도록 유념해야하는 것 같다.

해당 문제 같은 경우는, 오른쪽 포인터가 인덱스를 벗어나지 않도록 j += 1 문 이전에 

맨 오른쪽 원소를 추가하는 로직을 작성하였다.

시간복잡도는 O(N) 이다.

코드

s, p = map(int, input().split())
data = input()
acnt, ccnt, gcnt, tcnt = map(int, input().split())
answer = 0
# 두개의 포인터 지정
i = 0
j = p - 1

# 딕셔너리
dict = { 'A': 0, 'C': 0, 'G': 0, 'T': 0 }
targetStr = data[i:j]

for item in targetStr:
    dict[item] += 1

# 슬라이딩 윈도우
while j <= s-1:
    # 인덱스 초과 나니까 j+=1 하기전에, 오른쪽 원소 추가하는 로직을 먼저.
    dict[data[j]] += 1

    # 비밀번호 유효성 검사
    if dict['A'] >= acnt and dict['C'] >= ccnt and dict['G'] >= gcnt and dict['T'] >= tcnt:
        answer += 1

    dict[data[i]] -= 1 # 인덱스 맨 왼쪽 문자열 제거
    i += 1
    j += 1

print(answer)

문제링크

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

문제설명

9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

3

9
8 6
7
1 2
1 3
2 7
2 8

문제풀이

주어진 친족관계들을 기반으로, 입력 받은 두 값 a, b의 촌수를 계산하는 문제였다.

핵심 아이디어

1. 인접리스트 형태로 저장.

2. ★그래프에 저장할때 양방향임을 고려 (주어진 입력값은 한 방향관계만을 나타냄)

3. a, b의 촌수를 구한다는건 => 그래프를 그려놓고 생각해보면 a부터 b까지의 최단거리

   따라서 BFS를 활용

4. 촌수 카운트를 위해 queue에 (노드번호, depth) 튜플형태로 삽입

5. BFS를 시행하다가 구하고자 하는 노드에 도달하면 depth 반환

6. BFS 끝났는데도 도달 안하면 -1 반환

코드

from collections import deque

n = int(input())
a, b = map(int, input().split())
m = int(input())
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1)
queue = deque([])

# 양방향 그래프
for _ in range(m):
    s, e = map(int, input().split())
    graph[s].append(e)
    graph[e].append(s)

def BFS(a, b):
    queue.append([a, 0])
    visited[a] = 1

    while queue:
        cur, depth = queue.popleft()

        if cur == b:
            return depth

        for next in graph[cur]:
            if not visited[next]:
                queue.append([next, depth+1])
                visited[next] = 1

    return -1

print(BFS(a, b))

문제링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&problemLevel=3&problemLevel=4&contestProbId=AV5PobmqAPoDFAUq&categoryId=AV5PobmqAPoDFAUq&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=1

문제설명

달팽이는 1부터 N*N까지의 숫자가 시계방향으로 이루어져 있다.

다음과 같이 정수 N을 입력 받아 N크기의 달팽이를 출력하시오.


[예제]

N이 3일 경우,
 

N이 4일 경우,
 

[제약사항]

달팽이의 크기 N은 1 이상 10 이하의 정수이다. (1 ≤ N ≤ 10)


[입력]

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.

각 테스트 케이스에는 N이 주어진다.

문제풀이

이차원 배열에서의 주어진 조건(여기서는 시계방향)대로 인덱스에 접근하기 위한 구현 문제다.

방향전환, 범위체크 등이 가장 핵심이었으며

이전에 많이 비슷한 문제를 많이 풀어봤었지만 응용하려면 또 생각이 더 필요한 문제였던 것 같다.

코드

T = int(input())

for tc in range(1, T+1):
    N = int(input())
    arr = [[0 for _ in range(N)] for _ in range(N)]

    dx = [0, 1, 0, -1] # (동, 남, 서, 북)
    dy = [1, 0, -1, 0]
    dir = 0
    r, c = 0, 0

    for num in range(1, N*N+1):
        # 숫자 삽입
        arr[r][c] = num
        # 이동
        r += dx[dir]
        c += dy[dir]

        # 해당 지역이 범위를 벗어났거나 이미 값이 있다면
        if r < 0 or r >= N or c < 0 or c >= N or arr[r][c]:
            # 이전상태로 다시이동 
            r -= dx[dir]
            c -= dy[dir]

            # 방향 바꾸기(동->남, 남->서, 서->북, 북 >동)
            dir = (dir + 1) % 4

            # 이동
            r += dx[dir]
            c += dy[dir]

    print('#' + str(tc))
    for row in arr:
        print(*row)

문제링크

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

문제설명

2
5 6
0 0 1 0

30
30

3
3 4 5
1 0 1 0

35
17

문제풀이

코드

N = int(input())
arr = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())
maxValue = - int(1e9)
minValue = int(1e9)

def DFS(add, sub, mul, div, total, i):
    global maxValue, minValue

    if i == N:
        maxValue = max(maxValue, total)
        minValue=  min(minValue, total)
        return
    # 연산자 삽입
    if add:
        DFS(add-1, sub, mul, div, total+arr[i], i+1)
    if sub:
        DFS(add, sub-1, mul, div, total-arr[i], i+1)
    if mul:
        DFS(add, sub, mul-1, div, total*arr[i], i+1)
    if div:
        DFS(add, sub, mul, div-1, int(total/arr[i]), i+1)
            

DFS(add, sub, mul, div, arr[0], 1)
print(maxValue)
print(minValue)
# 연산자 우선순위 무시
# 1 2 3 4 5 6
# + + - * /

# N개의 수와 N-1개의 연산자가 주어질때 만들수있는 결과가 최대인것과 최소인것 구하기
# 완전탐색

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/43163

문제설명

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

begin              target                  words                                                                                                                           return

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

문제풀이

처음엔 DFS로 풀이에 접근하였으나, 역시 BFS가 더 익숙하고 쉽게 느껴진다.

문제를 풀때 요구사항에 맞는 알고리즘 및 자료구조를 최대한 빨리 캐치하는 능력이 중요한 것 같고,

문제를 많이 풀면서 향상 시킬 수 있도록 해야겠다.

핵심

단어를 target으로 만드는데에 필요한 최소횟수를 구하는것이므로 BFS활용이 좋아보인다.

1. 큐를 만들어 [시작단어, depth] 삽입

2. 한번에 한개의 알파벳만을 변환할 수 있으므로,

  words에 있는 후보 단어들과 큐에서 꺼낸 단어를 비교하여 한글자만 다르다면 큐에 삽입.

   그리고 depth 1증가

코드

from collections import deque

def solution(begin, target, words):
    answer = 0
    visited = [0] * (len(words))
    
    # BFS시행: 조건에 부합하는 변환과정을 위한 단어를 큐에 삽입해가기
    def BFS(data):
        queue = deque([[data, 0]]) # 단어, 변환횟수
        while queue:
            data, cnt = queue.popleft()
            
            if data == target:
                return cnt
          
            # words 배열의 단어중 한개만 변환하여 바꿀 수 있는 단어 탐색
            for i in range(len(words)):
                # 방문안한것중에서 탐색
                if not visited[i]:
                    check = 0
                    for j in range(len(words[i])):
                        # 다른 문자가 하나여야만 하므로
                        if data[j] != words[i][j]:
                            check += 1
                    if check == 1:
                        queue.append([words[i], cnt+1])
                        visited[i] = 1
        
        return 0
    
    answer = BFS(begin)
    return answer

문제링크

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

문제설명

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

9

문제풀이

시뮬레이션 문제로,

주어진 조건을 빠르고 정확하게 파악하는 것이 제일 중요한 것 같다.

이 부분은 앞으로도 남들보다 더 꾸준히 문제를 풀어 익숙해지려고 노력해야겠다.

핵심

1. 지도에서 움직이는 형태 구현. (상하좌우)

2. 방향 변환하는 함수 만들어서 활용

3. 자료구조 큐 활용

주의점

1. 이동후 현재좌표 갱신하기

BFS 문제중에 지도에서 움직이는 형태를 구현한 적이 많았는데 갱신된 좌표를 큐에 넣어서 해당좌표를 다시 꺼내 이용하여 문제가 없었지만,

지금은 직접 현재좌표를 갱신하는 추가코드가 필요하다!!

조금 안일하게 문제풀이에 임했지 않았나 싶다...

풀이 간략히 설명

- arr을 N * N 으로 만들고 사과가 있는 좌표에 1을 삽입 

- 방향 정보 저장은 딕셔너리를 활용

   direction[시간] = 문자정보  형태

- 뱀이 방문한 좌표는 arr[nx][ny] = 2. 

- 방문한 좌표마다 큐에 삽입하고, 방문한 좌표에 사과가 없다면

큐의 특성을 활용해 꼬리빼기(방문안함으로 처리)

- 이동할때마다 현재좌표 갱신!!

- 매초 마다 time을 증가시켜 direction의 키와 일치하는 시간이 되면 => 방향 변환 (함수로 구현)

코드

from collections import deque

N = int(input())
K = int(input())
arr = [[0 for _ in range(N)] for _ in range(N)]
dx = [0, -1, 0, 1]  # 각각 우 상 좌 하
dy = [1, 0, -1, 0]
directions = {}

# 입력값1) 사과 위치 정보 저장
for i in range(K):
    r, c = map(int, input().split())
    arr[r-1][c-1] = 1

L = int(input())
# 입력값2) 방향 변환 정보 저장
for i in range(L):
    x, d = input().split()
    directions[int(x)] = d

def rotateDir(index, str):  # 방향 나타내는 인덱스, 방향
    # 상3 하2 좌1 우0
    # L 왼쪽회전 => 우 -> 상(1) -> 좌(2) -> 하(3)
    # D 오른쪽회전 => 우(0) -> 하(3) -> 좌(2) -> 상(1)
    if str == 'L':
        result = (index + 1) % 4
    elif str == 'D':
        result = (index + 3) % 4
    return result

def start(x, y):
    dir = 0 # 처음은 오른쪽으로 향하니, 동을 나타내는 인덱스0 에 접근 위해 설정.
    queue = deque([(x, y)])
    arr[x][y] = 2
    time = 0
    
    while True:
        time += 1
        nx = x + dx[dir]
        ny = y + dy[dir]
        # 범위안에 있고 방문한 지역 아니라면
        if 0 <= nx < N and 0 <= ny < N and arr[nx][ny] != 2:
            queue.append((nx, ny))
            x, y = nx, ny
            # 사과가 있다면 꼬리 안뺌 그대로 늘림.
            if arr[nx][ny] == 1:
                arr[nx][ny] = 2   # 방문
            else:
                arr[nx][ny] = 2
                px, py = queue.popleft()
                arr[px][py] = 0
        else:
            break

        if time in directions.keys():
            dir = rotateDir(dir, directions[time])
    
    return time

print(start(0, 0))

문제링크

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

문제설명

4 6
a t c i s w

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

문제풀이

핵심

C개 문자 중  L개를 골라 암호를 만들어야하는데,

1. 최소 2개 자음과 1개 모음을 이용해야함.

2. 알파벳 순서로 나열된 암호여야함

풀이 과정

1. arr 오름차순 정렬

2. 정렬된 상태의 배열에서 반복문 시행. 각각 첫번째 원소부터 C-L 번째까지의 원소를 시작점으로 함수시행.

3. 후보리스트에 조건에 맞는 원소 삽입하고 재귀함수 호출

4. 후보리스트 길이가 원하는 길이라면, 암호조건에 부합하는지 체킹하고 리턴

5. 함수시행이 종료됐으므로, 백트래킹하여 다음 순번의 암호찾기.

코드

from itertools import combinations

L, C = map(int, input().split())
arr = list(input().split())
arr.sort()
# 입력예제1 => a, c, i, s, t, w

vowels = set(('a', 'e', 'i', 'o', 'u'))
# 최소 자음2개 모음1개 구성.
def check(arr):
    vcnt, ccnt = 0, 0
    for item in arr:
        if item in vowels:
            vcnt += 1
        else:
            ccnt += 1

    if vcnt >= 1 and ccnt >= 2:
        return True
    else:
        return False
    
def DFS(tmp):
    if len(tmp) == L:
        # 체킹
        if check(tmp):
            print(''.join(tmp))
            return
    
    # a c i s t w
    for i in range(len(tmp), C):
        if tmp[-1] < arr[i]:
            tmp.append(arr[i])
            DFS(tmp)
            tmp.pop()


for i in range(C-L+1):
    tmp = [arr[i]]
    DFS(tmp)

문제링크

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

문제설명

2 4
CAAB
ADCB

3

3 6
HFDFFB
AJHGDH
DGAGEH

6

문제풀이

백트래킹

DFS의 특성대로 탐색하다가, 더이상 솔루션이 될 수 없다고 판단되면 포기하고 다른 후보를 탐색하는 기법이다.

실수한 부분

1. 처음 DFS시행 전에 시작지점 좌표 방문, 알파벳체크 처리 잊지말자!

2. 불필요한 반복검사 줄이기. (아스키코드 활용하여 알파벳 => 숫자 변환하는 로직을 초반에 따로 빼자.)

    -> 이것도 시간초과에 한몫한듯.

코드

R, C = map(int, input().split())
arr = [list(input()) for i in range(R)]
visited = [[0 for _ in range(C)] for _ in range(R)] 
checked = [0] * 27
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
answer = 0

# 아스키코드 활용하여 알파벳 => 숫자로 바꾸기
for i in range(R):
    for j in range(C):
        arr[i][j] = ord(arr[i][j]) - 64

def DFS(x, y, cnt):
    global answer
    answer = max(cnt, answer)

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        # 범위 내에 있고, 방문안한 노드인지
        # arr[nx][ny]가 기존 알파벳들과 다른 알파벳인지
        if 0 <= nx < R and 0 <= ny < C and not visited[nx][ny]:
            if not checked[arr[nx][ny]]:
                visited[nx][ny] = 1
                checked[arr[nx][ny]] = 1
                DFS(nx, ny, cnt+1)
                visited[nx][ny] = 0
                checked[arr[nx][ny]] = 0
            

visited[0][0] = 1
checked[arr[0][0]] = 1
DFS(0, 0, 1)

print(answer)