이번 문제는 깊이우선탐색으로 해결하였다. 이전에 풀어본 양과 늑대 문제와 매우 유사했기 때문에 따로 설명은 생략해도 될 것 같다.

• 재귀 제한을 늘린다.
• dfs함수를 x, y를 인자로 갖도록 선언한다.
  -> k_cnt, v_cnt를 global로 선언한다.
  -> field[y][x]를 chk로 갱신한다.
  -> 4가지 방향에 대한 정보를 dy, dx 리스트에 짝지어 저장한다.
  -> 4번 반복하는 i에 대한 for문을 돌린다.
  --> ny에 y+dy[i]를 저장한다.
  --> nx에 x+dx[i]를 저장한다.
  --> 만약 ny, nx가 0보다 크거나 같고, ny가 r보다 작고, nx가 c보다 작고, field[ny][nx]가 chk, #이 아닐 경우,
  ---> 만약 field[ny][nx]가 k일 경우, k_cnt를 1 증가시킨다.
  ---> 만약 field[ny][nx]가 v일 경우, v_cnt를 1 증가시킨다.
  ---> dfs(ny, nx)를 재귀호출한다.
• r, c를 입력받는다.
• field 리스트를 선언한다.
• r번 반복하는 for문을 돌린다.
  -> field를 입력받는다.
• k_cnt, v_cnt를 0으로 선언한다.
• k, v를 0으로 선언한다.
• r번 반복하는 i에 대한 for문을 돌린다.
  -> c번 반복하는 j에 대한 for문을 돌린다.
  --> 만약 field[i][j]가 chk가 아닐 경우,
  ---> dfs(i, j)를 호출한다.
  ---> 만약 k_cnt가 v_cnt보다 크다면 k에 k_cnt를 더한다.
  ---> 그 외에는 v에 v_cnt를 더한다.
• k, v를 출력한다.

Code

import sys
sys.setrecursionlimit(10**9)
def dfs(y, x):
    global k_cnt
    global v_cnt
    field[y][x]='chk'
    dy=[0, 0, -1, 1]
    dx=[1, -1, 0, 0]
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if ny>=0 and nx>=0 and ny<r and nx<c and field[ny][nx]!='chk' and field[ny][nx]!='#':
            if field[ny][nx]=='k':
                k_cnt+=1
            if field[ny][nx]=='v':
                v_cnt+=1
            dfs(ny, nx)

r, c=map(int, input().split())
field=[]
for _ in range(r):
    field.append(list(map(str, input())))
k_cnt=0
v_cnt=0
k, v=0, 0
for i in range(r):
    for j in range(c):
        if field[i][j]!='chk':
            dfs(i, j)
            if k_cnt>v_cnt:
                k+=k_cnt
            else:
                v+=v_cnt
            k_cnt=0
            v_cnt=0
print(k, v)