[파이썬] 백준 - 실랜디

 

[파이썬] 백준 - 실랜디

매일 조금씩 풀기

하다보니까 부족한 유형 푸는중..

---

소수 (1312) - 실버5

A,B,N = map(int,input().split())
p,q = divmod(A,B)
for i in range(N):
    p,q = divmod(q*10,B)
    print(p)

조건 보고 overflow 발생하는지도 고려해야할듯.. 특히 나누기 or DP

무지성 나누기 후에 접근하는게 아니라 나누는 과정에서 접근하는게 포인트

---

1 만들기 (1463) - 실버3

n = int(input())
count = [0 for i in range(n)]
num = [i for i in range(1,n+1)]
temp = dict(zip(num,count))
temp[2]=1; temp[3]=1

for i in range(4,n+1):
    temp[i] = temp[i-1] + 1
    if i%2 == 0 :
        temp[i] = min(temp[i],temp[i//2]+1)
    if i%3 == 0 :
        temp[i] = min(temp[i],temp[i//3]+1)
print(temp[n])

DP 풀다보니까 보이긴 하네요

반복문 돌릴거라 리스트 보다는 접근할 때 딕셔너리가 빠를 것 같아서 딕셔너리 사용

---

비슷한 단어 (1411) - 실버2

N = int(input())
table = {}
for i in range(N): # 단어 입력받기
    string = input()
    capital = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
    temp,s = {},''
    
    for word in string : # 들어온 단어를 순서대로 대문자에 매핑 A~Z
        if word not in temp :
            temp[word] = capital[0]
            capital.pop(0) # 매핑됐으면 지우고 다음 매핑
        s += str(temp[word]) # 매핑 단어

    if s not in table : # 매핑단어을 tabel에 추가
        table[s] = 1
    else :
        table[s] += 1
        
similar = list(table.values())
answer = 0
for i in similar : # 매핑 쌍의 수 --> 조합
    answer += (i*(i-1))/2 # nC2
print(int(answer))

케이스가 적고 단어도 긴 편이 아니라 리스트를 써도 상관 없을듯

들어온 단어를 처음 나온 단어부터 A B C ... 순으로 매핑해서 하나의 단어로 만들고 딕셔너리에 숌 케이스를 추가해서 횟수 비교하기

랭킹이 높네요 ㅋㅋ

---

음하철도 구구팔 (1393) - 실버1

import math
xs,ys = map(int,input().split())
xe,ye,dx,dy = map(int,input().split())
d = math.gcd(dx,dy)
dx,dy = int(dx/d),int(dy/d)
temp_inner,temp_xy = [],[]
for i in range(200): # 범위 -100~100
    inner_abs = abs(dx*(xs-xe) + dy*(ys-ye))
    if abs(xe)>100 or abs(ye)>100 :
        break
    temp_inner.append(inner_abs)
    temp_xy.append([xe,ye]) 
    xe,ye = xe+dx,ye+dy
answer = temp_xy[temp_inner.index(min(temp_inner))]
print(answer[0],answer[1])

최대공약수로 step 최소단위로 맞춰주고

반복문으로 거리 멀어질때는 바로 탈출, 아니면 최소일 때

반복문에서 내적 조건에서도 루프를 걸어주는게 효율적이긴 한데 그냥 풀었습니다

---

타일링 (1793) - 실버2

while True:
    try:
        n = int(input())
        temp = {}
        temp[0],temp[1],temp[2] = 1,1,3
        for i in range(3,n+1):
            temp[i] = temp[i-1] + 2*temp[i-2]
        print(temp[n])
    except:
        break

1칸 2칸 계단오르기 문제랑 똑같은 문제.

2칸을 오르는 방법이 2가지라서 곱하기 2가 딸려나오는거만 체크하면 끝

2칸 채울 때 세로세로로 채우는건 1칸씩 두번 오르는거랑 똑같아서 3가지 경우가 아님

---

2xn 타일링 (11726) - 실버2

n = int(input())
temp = {}
temp[0],temp[1],temp[2] = 1,1,2
for i in range(3,n+1):
    temp[i] = temp[i-1] + temp[i-2]
print(temp[n]%10007)

---

2xn 타일링2 (11727) - 실버3

n = int(input())
temp = {}
temp[0],temp[1],temp[2] = 1,1,3
for i in range(3,n+1):
    temp[i] = temp[i-1] + 2*temp[i-2]
print(temp[n]%10007)

똑같은 문제 있길래 날먹..

---

동물원 (1309) - 실버1

n = int(input())
temp = {1:3,2:7}
for i in range(3,n+1):
    temp[i] = (2*temp[i-1]+temp[i-2])%9901
print(temp[n])

---

보물 (1026) - 실버4

n = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
A.sort(reverse=True)
B.sort()
answer = sum(map(lambda x,y : x*y,A,B))
print(answer)

어차피 내적 최소를 구하는거라 B 정렬 안한다는거는 큰 의미가 없다

---

흙길 보수하기 (1911) - 실버1

import sys
N,L = map(int,input().split())
max_end,count = 0,0
info = []
for i in range(N):
    start,end = map(int,sys.stdin.readline().split())
    info.append([start,end])
info.sort()

now,idx,count = info[0][0],0,0
while now < info[-1][1] :
    p,q = divmod(info[idx][1]-now,L)
    if info[idx][0]<=now<info[idx][1] :
        if q==0:
            now += L*p
            count += p
        else :
            now += L*(p+1)
            count += (p+1)

    else :
        idx += 1
        if now < info[idx][0] :
            now = info[idx][0]
print(count)

프로그래머스 레벨1 덧칠하기랑 비슷한 문제

범위가 10^9여서 리스트에 True/False로 할당하거나 반복 연산을 해서 점프 형식으로 가면 메모리/시간초과한다.

어케 알았냐면...

인덱스를 받아서 몇개의 판자가 들어가는지 계산 바로해야함

 

---

숨바꼭질 (1697) - 실버1

from collections import deque

def bfs(N,K):
    MAX = 100001
    time = [0] * MAX
    q = deque([N])
    
    while q:
        now = q.popleft()
        if now == K :
            return time[now]
        for nexts in (now-1,now+1,now*2):
            if 0 <= nexts < MAX and time[nexts]==0:
                time[nexts] = time[now] + 1
                q.append(nexts)

N,K = map(int,input().split())
print(bfs(N,K))

현재 값을 넣었을 때 다음 값들이 범위 내에 있고 아직 탐색하지 않았으면 t+1 값을 넣어주기

---

음식물 피하기 (1743) - 실버1

import sys
sys.setrecursionlimit(10**6)
N,M,K = map(int,input().split())
room = [[True]*M for i in range(N)]

for i in range(K):
    x,y = map(int,sys.stdin.readline().split())
    room[x-1][y-1] = False

def dfs(x,y):
    if x<0 or x>=N or y<0 or y>=M :
        return 0
    if room[x][y] == False :
        room[x][y] = True
        return 1 + dfs(x-1,y) + dfs(x+1,y) + dfs(x,y-1) + dfs(x,y+1)
    return 0

answer = 0
for i in range(N):
    for j in range(M):
        answer = max(answer,dfs(i,j))
print(answer)

좌표평면 받아서 푸는 기본적인 DFS문제는 쉬운듯

---

단지번호 붙이기 (2667) - 실버1

import sys
sys.setrecursionlimit(10**6)
N = int(input())
apt = []
for i in range(N):
    s = list(sys.stdin.readline())
    apt.append(s)
    
def dfs(x,y):
    if x<0 or x>=N or y<0 or y>=N :
        return 0
    if apt[x][y] == '1' :
        apt[x][y] = '0'
        return 1 + dfs(x-1,y) + dfs(x+1,y) + dfs(x,y-1) + dfs(x,y+1)
    return 0

count,result = 0,[]
for i in range(N):
    for j in range(N):
        if apt[i][j] == '1':
            result.append(dfs(i,j))
            count += 1
result.sort()

print(count)
for r in result:
    print(r)

좌표평면 받아서 푸는 기본적인 DFS문제는 쉬운듯

같은 방법으로 푸는데 리스트에 DFS돌려서 만든 군집 사이즈를 넣어서 정렬하기

---

유기농 배추 (1012) - 실버2

import sys
sys.setrecursionlimit(10**6)

def dfs(x,y):
    if x<0 or y<0 or x>=N or y>=M :
        return 0
    if land[x][y] == True :
        land[x][y] = False
        return 1+dfs(x-1,y)+dfs(x+1,y)+dfs(x,y-1)+dfs(x,y+1)
    return 0

T = int(input())
for t in range(T) :
    M,N,K = map(int,input().split())
    land = [[False]*M for i in range(N)]

    for i in range(K):
        x,y = map(int,sys.stdin.readline().split())
        land[y][x] = True

    count = 0
    for i in range(N):
        for j in range(M):
            if land[i][j] == True :
                dfs(i,j)
                count += 1
    print(count)

 

---

그림 (1926) - 실버1

import sys
sys.setrecursionlimit(10**6)

h,w = map(int,sys.stdin.readline().split())
painting = []
for i in range(h):
    temp = list(map(int,sys.stdin.readline().split()))
    painting.append(temp)

def dfs(x,y):
    if x<0 or y<0 or x>=w or y>=h :
        return 0
    if painting[y][x] == 1 :
        painting[y][x] = 0
        return 1+dfs(x-1,y)+dfs(x+1,y)+dfs(x,y-1)+dfs(x,y+1)
    return 0

count,max_area = 0,0
for i in range(h):
    for j in range(w):
        if painting[i][j] == 1 :
            count += 1
            area = dfs(j,i)
            if area > max_area :
                max_area = area
            
print(count)
print(max_area)

---

섬의 개수 (4963) - 실버2

import sys
sys.setrecursionlimit(10**6)

def dfs(x,y):
    if x<0 or x>=w or y<0 or y>=h :
        return 0
    if land[y][x] == 1 :
        land[y][x] = 0
        return 1+dfs(x+1,y)+dfs(x+1,y+1)+dfs(x+1,y-1)+dfs(x-1,y)+dfs(x-1,y+1)+dfs(x-1,y-1)+dfs(x,y-1)+dfs(x,y+1)
    return 0

while True :
    w,h = map(int,sys.stdin.readline().split())
    if w==0 and h==0 :
        break
    land = []
    for i in range(h):
        temp = list(map(int,sys.stdin.readline().split()))
        land.append(temp)

    count = 0
    for i in range(h):
        for j in range(w):
            if land[i][j] == 1 :
                count += 1
                dfs(j,i)
    print(count)

---

영역구하기 (2583) - 실버1

import sys
sys.setrecursionlimit(10**6)

def dfs(x,y):
    if x<0 or y<0 or x>=w or y>=h :
        return 0
    if area[y][x] == 1 :
        area[y][x] = 0
        return 1+dfs(x-1,y)+dfs(x+1,y)+dfs(x,y-1)+dfs(x,y+1)
    return 0

h,w,s = map(int,sys.stdin.readline().split())
area = [[1]*w for i in range(h)]        
for i in range(s):
    ax,ay,bx,by = map(int,sys.stdin.readline().split())
    for x in range(min(ax,bx),max(ax,bx)):
        for y in range(min(ay,by),max(ay,by)):
            if area[y][x] == 1 :
                area[y][x] = 0

answer = []
for i in range(h):
    for j in range(w):
        if area[i][j] == 1:
            answer.append(dfs(j,i))
answer.sort()
print(len(answer))
print(*answer)

---

현수막 (14716) - 실버1

import sys
sys.setrecursionlimit(10**6)

h,w = map(int,sys.stdin.readline().split())
def dfs(x,y):
    if x<0 or x>=w or y<0 or y>=h :
        return 0
    if banner[y][x] == 1 :
        banner[y][x] = 0
        return 1+dfs(x+1,y)+dfs(x+1,y+1)+dfs(x+1,y-1)+dfs(x-1,y)+dfs(x-1,y+1)+dfs(x-1,y-1)+dfs(x,y-1)+dfs(x,y+1)
    return 0

banner = []
for i in range(h):
    temp = list(map(int,sys.stdin.readline().split()))
    banner.append(temp)

count = 0
for i in range(h):
    for j in range(w):
        if banner[i][j] == 1 :
            count += 1
            dfs(j,i)
print(count)

 

---

영상처리 (21938) - 실버2

import sys
sys.setrecursionlimit(10**6)
    
N,M = map(int,sys.stdin.readline().split())
arr = []
for i in range(N):
    temp = list(map(int,sys.stdin.readline().split()))
    temp1 = []
    for j in range(0,3*M,3):
        temp1.append(sum(temp[j:j+3]))
    arr.append(temp1)
    
th = 3*int(input())
for i in range(N):
    for j in range(M):
        if arr[i][j] >= th :
            arr[i][j] = 255
        else :
            arr[i][j] = 0

def dfs(x,y):
    if x<0 or y<0 or x>=M or y>=N :
        return 0
    if arr[y][x] == 255 :
        arr[y][x] = 0
        return 1+dfs(x-1,y)+dfs(x+1,y)+dfs(x,y-1)+dfs(x,y+1)
    return 0
count = 0
for i in range(N):
    for j in range(M):
        if arr[i][j] == 255 :
            count += 1
            area = dfs(j,i)
print(count)

---

연결 요소의 개수 (11724) - 실버2

import sys
sys.setrecursionlimit(10**6)
N,T = map(int,sys.stdin.readline().split())

connect = [[] for i in range(N+1)]
visit = [False for i in range(N+1)]

for i in range(T):
    x,y = map(int,sys.stdin.readline().split())
    connect[x].append(y)
    connect[y].append(x)
    
def dfs(x):
    if visit[x] == False :
        visit[x] = True
        for node in connect[x]:
            if not visit[node]:
                dfs(node)
count = 0
for i in range(1,N+1):
    if not visit[i]:
        dfs(i)
        count += 1
print(count)

2차원 dfs 끝내고 무방향 / 방향 그래프

무방향 그래프이므로 connect에 양 쪽 원소를 추가

중복 탐색을 방지하기 위해 visit이 False일 때만 진행

---

바이러스 (2606) - 실버3

def dfs(x,count):
    visit[x] = True
    for i in relation[x]:
        if not visit[i]:
            count = dfs(i,count+1)
    return count

N = int(input())
T = int(input())
relation = [[] for i in range(N+1)]
visit = [False for i in range(N+1)]

for i in range(T):
    x,y = map(int,input().split())
    relation[x].append(y)
    relation[y].append(x)

print(dfs(1,0))

 

---

촌수 계산 (2644) - 실버2

from collections import deque
import sys
sys.setrecursionlimit(10**4)

people = int(input())
a,b = map(int,input().split())
T = int(input())

graph = [[] for i in range(people+1)]
for i in range(T):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

def bfs(node1,node2):
    visit = [0]*(people+1)
    q = deque([node1])
    visit[node1] = 1
    
    while q:
        v = q.popleft()
        if v == node2:
            return visit[node2]-1
        
        for i in graph[v]:
            if not visit[i]:
                q.append(i)
                visit[i] = visit[v]+1
    return -1

print(bfs(a,b))

자기 자신은 0촌으로 생각하기 때문에 도착 노드에 도착했을 때 -1 해줘야함

---

쉬운 최단거리 (14940) - 실버1

import sys
from collections import deque
h,w = map(int,sys.stdin.readline().split())
arr = []
for i in range(h):
    temp = list(map(int,sys.stdin.readline().split()))
    arr.append(temp)
    if 2 in temp :
        x = temp.index(2)
        y = i

visit = [[False]*w for i in range(h)]
answer = [[0]*w for i in range(h)]
step = [[1,0,-1,0],[0,1,0,-1]]

def bfs(x,y):
    q = deque()
    q.append([x,y])
    visit[y][x] = True
    
    while q:
        now = q.popleft()
        
        for i in range(4):
            next_x = now[0]+step[0][i]
            next_y = now[1]+step[1][i]
            
            if (0<=next_y<h) and (0<=next_x<w) and visit[next_y][next_x] == False :
                if arr[next_y][next_x] == 0 :
                    answer[next_y][next_x] = 0
                    
                elif arr[next_y][next_x] == 1 :
                    visit[next_y][next_x] = True
                    answer[next_y][next_x] = answer[now[1]][now[0]] + 1
                    q.append([next_x,next_y])
                    
    for i in range(h):
        for j in range(w):
            if visit[i][j] == False and arr[i][j] == 1:
                answer[i][j] = -1

bfs(x,y)
for i in answer :
    print(*i)

호흡이 길어서 조금 빡세네요.

input 넣는 와중에 2 위치를 찾아서 탐색 시작 할 때 시작 위치 True만들고 탐색 시작.

탐색 끝난 후 탐색되지 않았고 땅인 부분은 -1로

---

미로 탐색 (2178) - 실버1

from collections import deque
import sys

h, w = map(int,sys.stdin.readline().split())
arr = []
for i in range(h):
    arr.append(list(sys.stdin.readline()))
    
visit = [[False]*w for i in range(h)]
answer = [[0]*w for i in range(h)]
step = [[1,-1,0,0],[0,0,1,-1]]

def bfs(a,b):
    q = deque()
    q.append([0, 0])
    visit[0][0] = True

    while q:
        now = q.popleft()

        for i in range(4):
            next_x = now[0] + step[0][i]
            next_y = now[1] + step[1][i]

            if 0 <= next_x < w and 0 <= next_y < h and visit[next_y][next_x] == False:
                if arr[next_y][next_x] == '1':
                    visit[next_y][next_x] = True
                    answer[next_y][next_x] = answer[now[1]][now[0]]+1
                    q.append([next_x, next_y])

    return answer[b-1][a-1]+1

print(bfs(w,h))

---

안전 영역 (2468) - 실버1

import sys
import copy
sys.setrecursionlimit(10**6)

n = int(input())
arr,table = [],{}
for i in range(n):
    arr.append(list((map(int,sys.stdin.readline().split()))))
    for j in arr[-1]:
        table[j] = 0

temp = list(table.keys())
temp.sort()

def dfs(x,y,h):
    if x<0 or y<0 or x>=n or y>= n:
        return 0
    if arr_h[y][x] > h:
        arr_h[y][x] = 0
        return 1+dfs(x-1,y,h)+dfs(x+1,y,h)+dfs(x,y-1,h)+dfs(x,y+1,h)
    return 0

if len(temp)== 1:
    print(1)
else: 
    for h in temp:
        count = 0
        arr_h = copy.deepcopy(arr)
        for i in range(n):
            for j in range(n):
                if arr_h[i][j] > h:
                    dfs(j,i,h)
                    count += 1
        table[h] = count
    print(max(table.values()))

처음에 입력받은 arr을 계속 써야해서 deepcopy를 썼다.

처음에 그냥 copy 썼는데 참조 오류나서 삽질을 좀 했다.

추가 조건에서 모두 안잠기는 경우가 있다고 했으니 높이가 모두 같으면 dfs 돌릴 필요 없이 1

반복문 실행 시에도 모든 높이에 대해서 진행하는 것이 아니라 입력이 들어 올 때 경계값을 temp에 넣어주고 이 값에 대해서만 돌려주면 된다.

---

나이트의 이동 (7562) - 실버1

from collections import deque

T = int(input())

for i in range(T):
    n = int(input())
    arr = [[0]*n for i in range(n)]
    visit = [[False]*n for i in range(n)]
    
    start = list(map(int,input().split()))
    end = list(map(int,input().split()))
    step = [[2,2,1,1,-1,-1,-2,-2],[1,-1,2,-2,2,-2,1,-1]]
    
    q = deque()
    q.append(start)
    visit[start[1]][start[0]] = True
    while q :
        now = q.popleft()
        if now == end:
            print(arr[now[1]][now[0]])
            break
            
        for i in range(8):
            next_x = now[0] + step[0][i]
            next_y = now[1] + step[1][i]

            if 0<=next_x<n and 0<=next_y<n and visit[next_y][next_x] == False:
                visit[next_y][next_x] = True
                arr[next_y][next_x] = arr[now[1]][now[0]]+1
                q.append([next_x, next_y])

---

A → B (16953) - 실버2

from collections import deque

A,B = map(int,input().split())
table = {}

def bfs(A,B):
    
    q = deque([A])
    count = 1
    table[A] = count

    while q:
        now = q.popleft()
        
        if now == B:
            return table[now]
        
        for nexts in (now*2,now*10+1):
            if nexts <= B and nexts not in table:
                table[nexts] = table[now] + 1
                q.append(nexts)
                
    return -1

print(bfs(A,B))

처음 알았는데 큐를 사용할때는 immutable 보장을 위해서 튜플 사용한다는 점...

---

바닥장식 (1388) - 실버4

import sys
sys.setrecursionlimit(10**6)

N,M = map(int,sys.stdin.readline().split())
arr = []
for i in range(N):
    arr.append(list(sys.stdin.readline()))
visit = [[False]*M for i in range(N)]

def dfs_horizon(x,y):
    if x<0 or y<0 or x>=M or y>=N :
        return 0
    if visit[y][x] == False and arr[y][x]== '-':
        visit[y][x] = True
        arr[y][x] = 0
        return dfs_horizon(x+1,y)
    return 0

def dfs_vertical(x,y):
    if x<0 or y<0 or x>=M or y>=N :
        return 0 
    if visit[y][x] == False and arr[y][x]== '|':
        visit[y][x] = True
        arr[y][x] = 0
        return dfs_vertical(x,y+1)
    return 0

count = 0
for i in range(N):
    for j in range(M):
        if arr[i][j] == '-':
            count += 1
            dfs_horizon(j,i)
        elif arr[i][j] == '|':
            count += 1
            dfs_vertical(j,i)
print(count)

---

효율적인 해킹 (1325) - 실버1

import sys
from collections import deque

N,T = map(int,sys.stdin.readline().split())
graph = [[] for i in range(N+1)]
visit = [False]*(N+1)
table = dict(zip(range(1,N+1),[0]*(N+1)))

for i in range(T):
    x,y = map(int,sys.stdin.readline().split())
    graph[y].append(x)

def bfs(x):
    count = 0
    q = deque([x])
    visit = [False for i in range(N+1)]
    visit[x] = True

    while q:
        now = q.popleft()

        for nexts in graph[now]:
            if not visit[nexts]:
                visit[nexts] = True
                count += 1
                q.append(nexts)
    return count

max_count = 0
answer = []
for i in range(1,N+1):
    visit = [False]*(N+1)
    count = bfs(i)
    if count > max_count:
        max_count = count
        answer = [i] 
    elif count == max_count:
        answer.append(i)
answer.sort()
print(*answer)

문제는 그냥 방향성 있는 그래프 푸는거라 어렵지는 않았는데 시간제한이 빡빡하다

DFS로 10트 넘게해서 BFS로 바꾸고 pypy3쓰고 구글링 엄청해서 풀었다. 다신 안풀고싶은 문제 1위

---

케빈 베이컨의 6단계 법칙 (1389) - 실버1

from collections import deque

N,M = map(int,input().split())
relation = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    relation[b].append(a)
    relation[a].append(b)
    
def bfs(x):
    step = [0]*(N+1)
    visit[x] = True
    q = deque()
    q.append(x)
    while q:
        now = q.popleft()
        for nexts in relation[now]:
            if not visit[nexts]:
                visit[nexts] = True
                step[nexts] = step[now]+1
                q.append(nexts)
    return sum(step)

table = {}
for i in range(1,N+1):
    visit = [False]*(N+1)
    table[i] = bfs(i)
    
answer = [key for key,value in table.items() if value == min(table.values())]
print(min(answer))

---

1로 만들기 2 (12852) - 실버1

from collections import deque
def bfs(X):
    q = deque([X])
    visit = [False]*(N+1)
    path = [0]*(N+1)
    while q:
        now = q.popleft()
        if now == 1 :
            return step[now], path
        nexts = [now-1]
        if now%2 == 0 :
            nexts.append(int(now/2))
        if now%3 == 0 :
            nexts.append(int(now/3))
            
        for i in nexts:
            if not visit[i]:
                visit[i] = True
                q.append(i)
                step[i] = step[now] + 1
                path[i] = now

N = int(input())
step = [0]*(N+1)
min_step, path = bfs(N)

now = 1
shortcut = [now]
while now != N:
    now = path[now]
    shortcut.append(now)
    
print(min_step)
print(*shortcut[::-1])

 

17 16 8 4 3 1
[0, 3, 4, 4, 8, 15, 7, 8, 16, 0, 0, 12, 13, 14, 15, 16, 17, 0]

17 넣으면 이런식으로 나오는데 now=1 설정하고 path에 접근해서 3 얻고 3번째 인덱스인 4로 접근, 4번째 인덱스 8로 접근 8번째 인덱스 16으로 접근 이런식으로 반복해서 경로 찾기

---

전쟁 - 전투 (1303) - 실버1

import sys
sys.setrecursionlimit(10**6)

w,h = map(int,sys.stdin.readline().split())
arr= []
for i in range(h):
    arr.append(list(sys.stdin.readline().strip()))

def dfs_W(x,y):
    if x<0 or y<0 or x>=w or y>=h :
        return 0
    if not visit[y][x] and arr[y][x]=='W':
        visit[y][x] = True
        arr[y][x] = 0
        return 1+dfs_W(x-1,y)+dfs_W(x+1,y)+dfs_W(x,y-1)+dfs_W(x,y+1)
    return 0
    
def dfs_B(x,y):
    if x<0 or y<0 or x>=w or y>=h :
        return 0    
    if not visit[y][x] and arr[y][x]=='B':
        visit[y][x] = True
        arr[y][x] = 0
        return 1+dfs_B(x-1,y)+dfs_B(x+1,y)+dfs_B(x,y-1)+dfs_B(x,y+1)
    return 0

visit = [[False]*w for i in range(h)]
table = {'W':0,'B':0}

for i in range(h):
    for j in range(w):
        if arr[i][j] == 'W':
            table['W'] += dfs_W(j,i)**2
        if arr[i][j] == 'B':
            table['B'] += dfs_B(j,i)**2
            
print(table['W'],table['B'])