[파이썬] 1303. 전쟁 - 전투

문제

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다.

그러나 당신의 병사들은 하얀 옷을 입고, 적국의 병사들은 파란옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다.

문제는, 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

N명이 뭉쳐있을 때는 N^2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.

입력

첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 병사가 한 명 있다. (B는 파랑, W는 흰색이다.)

출력

첫 번째 줄에 당신의 병사의 위력의 합과 적국의 병사의 위력의 합을 출력한다.

예제 입력 1 

5 5

WBWWW

WWWWW

BBBBB

BBBWW

WWWWW

예제 출력 1 

130 65

 

 

👩‍🦰 나의 풀이

 

import sys
input=sys.stdin.readline
N, M=map(int, input().split())  # 전쟁터의 가로와 세로 크기
area=[input().rstrip() for _ in range(M)]
pos_x=[0, -1, 1, 0]
pos_y=[1, 0, 0, -1]
visited=[[0]*N for _ in range(M)]

def dfs(x, y, color) :
    global cnt
    for i, j in zip(pos_x, pos_y) :
        dx=i+x
        dy=j+y
        if 0 <= dx < M and 0 <= dy < N :
            if not visited[dx][dy] and area[dx][dy] == color :
                visited[dx][dy]=1
                cnt+=1
                dfs(dx, dy, color)
    return

W=0; B=0
for x in range(M) :
    for y in range(N) :
        cnt=1
        if not visited[x][y] :
            if area[x][y] == 'W' :
                visited[x][y] = 1
                dfs(x, y, 'W')
                W+=cnt**2
            else :
                visited[x][y]=1
                dfs(x, y, 'B')
                B+=cnt**2

print(W, B)

 

dfs를 이용한 풀이

전역변수 cnt의 값을 함수내에서 바꾸기 위해 global 사용

이중 for문을 사용해서 방문하지 않은 값을 dfs함수에 파라미터로 넣어 호출한다. 

dfs 함수에서는 전달받은 좌표의 상하좌우를 탐색한다.

같은 팀이고 방문한적 없으면 재귀호출한다.

 

 

# 실패
import sys

N, M = map(int, sys.stdin.readline().split())  # 가로, 세로
color = list()
for m in range(M):
    color.append(sys.stdin.readline())


def dfs(w):
    #visited = [[0] * N for _ in range(M)]
    dp = [[0] * N for _ in range(M)]
    #stack = [(0, 0)]

    for x in range(N):
        ans=1
        for y in range(M) :
        #x, y = stack.pop()
            #if not visited[x][y]:
            #visited[x][y] = 1
            if color[x][y] == w:
                dp[x][y] += ans
                ans += 1
            else:
                ans = 1

dfs("W")

 

dp로 풀어볼려고 했다. 

하지만 구멍이 있는 점화식 ㅠ

WBWWW

WWWWW를

1	0	1	2	3
1	2	3	4	5

행에서 가장 큰 수끼리 더하면 8

(0, 0)의 1을 어떻게 포함시킬지 몰라서,,

 

 

👧 다른 사람 풀이

 

# https://velog.io/@eujin/Algorithm-%EB%B0%B1%EC%A4%80-1303-%EC%A0%84%EC%9F%81-%EC%A0%84%ED%88%AC-DFSBFS-Python
from collections import deque

m,n = map(int, input().split())	# 가로, 세로
graph = [list(input().strip()) for _ in range(n)]	# 병사들의 옷색
w,b=0,0

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(x,y,team):
    queue = deque()
    queue.append((x,y))
    count = 0
    #graph[x][y] == 0	왜 있는걸까??
    while queue:
        x, y = queue.popleft()
        for i in range(4):	# 상하좌우 탐색
            nx = x+dx[i]
            ny = y+dy[i]
            if nx<0 or ny<0 or nx>=n or ny>=m:	# 범위 체크
                continue
            if graph[nx][ny] != 0 and graph[nx][ny] == team: # 방문한 적 없고 같은 팀
                queue.append((nx,ny))
                graph[nx][ny] = 0	# 방문 처리
                count += 1
    return (1 if count==0 else count)	# 상하좌우로 같은 팀이 없으면 자기 자신만 세서 1

for i in range(n):
    for j in range(m):
        if graph[i][j] != 0:	# 방문한 적 없으면
            if graph[i][j] == 'W':
                w += bfs(i,j,graph[i][j])**2
            else:
                b += bfs(i,j,graph[i][j])**2
print(w,b)

 

bfs로 구현

bfs는 최단 경로를 찾는 문제에 많이 쓰임.

이 문제도 거리랑 관련있어서 bfs가 dfs보다 적합한 듯. 

리스트를 벗어나지 않는 범위 내에서 상하좌우로 탐색한다.

방문한 후 0으로 바꿔줌.

 

import sys
read=sys.stdin.readline

N, M=map(int, read().rstrip().split())  # 가로, 세로

field=[]
friend=[]
enemy=[]
for _ in range(M) :
    field.append(list(read().rstrip()))

def dfs(x, y, flag, color, depth) :
    for dx, dy in (-1, 0), (1, 0), (0, -1), (0, 1) :
        move_x=x+dx
        move_y=y+dy
        if move_x < 0 or move_x >= M or move_y < 0 or move_y >= N : # 범위 체크
            continue

        if flag[move_x][move_y] and field[move_x][move_y] == color :    # 방문한 적 없고 같은 팀이면
            flag[move_x][move_y]=False      # 방문 처리
            color_dict[color]+=1
            dfs(move_x, move_y, flag, color, depth+1)

flag=[[True]*N for _ in range(M)]   # 방문 기록
color_dict={"W":0, "B":0}
ans=[0, 0]

for i in range(M) :
    for j in range(N) :
        if flag[i][j] :
            color=field[i][j]
            color_dict[color]=1
            flag[i][j]=False
            dfs(i, j, flag, color, 0)
            if color == "W" :
                ans[0] += color_dict[color]**2
            else :
                ans[1]+=color_dict[color]**2

print(*ans)

 

재귀를 이용한 dfs 구현

로직은 같음.