[백준][Python] 1303 전쟁 - 전투

그래프, bfs / 실버 1

⚔️

https://www.acmicpc.net/problem/1303

1303번: 전쟁 - 전투

 

내 풀이

from collections import deque

def bfs(x, y):
    global our_power, enemy_power
    power = 1
    visited[x][y] = True
    q = deque()

    current = arr[x][y] # 현재 병사 (B or W)
    q.append((x, y))

    while q:
        cx, cy = q.popleft()

        for k in range(4):
            nx, ny = cx + dx[k], cy + dy[k]
            
            if nx < 0 or nx >= M or ny < 0 or ny >= N: # 범위를 벗어난 경우
                continue

            if current == arr[nx][ny] and not visited[nx][ny]: # 같은 편의 병사 + 방문하지 않은 경우
                power += 1
                visited[nx][ny] = True
                q.append((nx, ny))

    if current == 'W': # 우리 병사
        our_power += pow(power, 2)
    else: # 적국 병사
        enemy_power += pow(power, 2)


N, M = map(int, input().split()) # 가로 크기, 세로 크기
arr = [[] * N for _ in range(M)]
visited = [[False] * N for _ in range(M)]

for i in range(M):
    arr[i] = list(input())

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

our_power = 0 # 우리 병사의 위력
enemy_power = 0 # 적국 병사의 위력

for i in range(M):
    for j in range(N):
        if not visited[i][j]:
            bfs(i, j)

print(our_power, enemy_power)

bfs(너비 우선 탐색)으로 풀었다.

 

 

코드 설명

 

같은 팀의 병사들은 모일수록 강해진다.

이때, 뭉쳐있다는 것은 상하좌우로 연결되어 있음을 의미한다.

상하좌우로 이동하기 위한 좌표를 리스트에 저장한다.

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

 

✔️ bfs 함수

 

power: 현재 병사의 위력을 저장하는 변수

 

위력을 계산하기 전에 우리 병사인지, 적국 병사인지를 먼저 알아야 한다.

current는 B(적국 병사), W(우리 병사) 둘 중 하나가 될 것이다.

current = arr[x][y] # 현재 병사 (B or W)
    q.append((x, y))

 

같은 편의 병사이면서, 방문하지 않은 병사인 경우에만 power를 1 증가시켜 주고, 방문 처리 + deque에 추가!

다른 편의 병사를 만났다면, 무시한다.

if current == arr[nx][ny] and not visited[nx][ny]: # 같은 편의 병사 + 방문하지 않은 경우
    power += 1
    visited[nx][ny] = True
    q.append((nx, ny))

 

while문이 끝난 뒤, power 제곱의 값을 우리 병사라면 our_power에  더해주고, 적국 병사라면 enemy_power에 더해준다.

if current == 'W': # 우리 병사
    our_power += pow(power, 2)
else: # 적국 병사
    enemy_power += pow(power, 2)

 

 

어려웠던 점

 

기본적인 bfs 문제에서 많이 벗어나지 않아서, 문제를 이해하고 해결하는 데에는 큰 어려움이 없었는데,

N과 M을 입력받을 때, 일반적인 문제들과 다르게 가로크기, 세로크기 순으로(반대로) 입력을 받아서 헷갈렸다.

예전부터 이 부분이 계속 헷갈린다.. 확실히 짚고 넘어가야 나중에 시간낭비 안 할 듯?

그래서 처음에 런타임 에러(IndexError)가 발생했었음..!

OMG