코딩테스트/프로그래머스
[백준] 1303번 전쟁-전투 / 파이썬(python)
Jiwon_C
2021. 5. 25. 00:43
# 문제 링크
https://www.acmicpc.net/problem/1303
1303번: 전쟁 - 전투
첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는
www.acmicpc.net
# Soultion
dfs를 이용하여 2가지 케이스(W,H)로 이어진 부분의 개수를 구함
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
n,m = map(int,input().split())
graph = []
w_location = []
b_location = []
for i in range(m):
graph.append(list(map(str,input())))
for j in range(n):
if graph[i][j]=='W':
w_location.append([i,j])
else:
b_location.append([i,j])
dx = [1,-1,0,0]
dy = [0,0,1,-1]
def dfs(x,y,color):
global cnt
cnt+=1
for i in range(4):
xx = x+dx[i]
yy = y+dy[i]
if 0<=xx<m and 0<=yy<n and graph[xx][yy]==color and visited[xx][yy]==0:
visited[xx][yy] = visited[x][y]+1
dfs(xx,yy,color)
# W 체크
visited = [[0]*n for _ in range(m)]
cnt_w = 0
for x,y in w_location:
cnt = 0
if visited[x][y]==0:
visited[x][y] = 1
dfs(x,y,'W')
cnt_w += cnt*cnt
print(cnt_w,end=' ')
# B 체크
visited = [[0]*n for _ in range(m)]
cnt_b = 0
for x,y in b_location:
cnt = 0
if visited[x][y]==0:
visited[x][y] = 1
dfs(x,y,'B')
cnt_b += cnt*cnt
print(cnt_b,end=' ')
|
cs |