[python3] 전쟁-전투 DFS풀이

전쟁 - 전투 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

9716

3740

3018

37.706%

문제

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

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

입력

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

출력

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

예제 입력 1 복사

5 5
WBWWW
WWWWW
BBBBB
BBBWW
WWWWW

예제 출력 1 복사

 

130 65

 

 

def dfs(x,y):
    
    global cnt
    graph[x][y]='E'
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        
        if -1<nx<m and -1<ny<n:
            if graph[nx][ny]=='W':
                graph[nx][ny]=1
                cnt+=1
                dfs(nx,ny)


    return cnt

def dfs2(x,y):
    
    global enemy_cnt
    graph[x][y]='E'
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        
        if -1<nx<m and -1<ny<n:
            if graph[nx][ny]=='B':
                graph[nx][ny]='E'
                enemy_cnt+=1
                dfs2(nx,ny)


    return enemy_cnt
            

n,m=map(int,input().split())

# 각 노드가 연결된 정보를 표현
graph = [list(map(str, input())) for _ in range(m)]
    
# 상하좌우
dx=[-1,1,0,0]
dy=[0,0,-1,1]
cnt=1
enemy_cnt=1
our_team=[]
enemy_team=[]
for i in range(m):
    for j in range(n):
        if graph[i][j]=='W':
            dfs(i,j)
            our_team.append(cnt**2)
            cnt=1
            
for i in range(m):
    for j in range(n):
        if graph[i][j]=='B':
            dfs2(i,j)
            enemy_team.append(enemy_cnt**2)
            enemy_cnt=1
            
print(sum(our_team),sum(enemy_team))

 

x,y를 입력받는다 예를들어 6,4라면

 

000000

000000

000000

000000

 

와 같은 형태가 될것이다.

 

그리고 해당하는 블록 상하좌우에 B 또는 W가 있을계속 계속 탐색을 진행하면서 dfs를 돌리고 cnt값을 1씩 카운트

시켜준다. 그리고 붙어있는 불럭이 전부 카운트가 될경우 다시 카운트를 1로 초기화 시키고 다시 해당하는 값을

찾는 방법으로 풀었다.

 

DFS BFS를 배운지 얼마 되지않았지만 점점 실력이 느는 느낌이 든다. 열심히 해봐야겠다.