위 풀이의 Python 버전입니다. 크게 다를건 없고 Python이 코드라인이 훨씬 적습니다.
import sys
from collections import deque
nm = sys.stdin.readline().split(' ')
M = int(nm[0])
N = int(nm[1])
B, W = 0, 0
maps = []
delta = [[-1, 0],[1, 0],[0, -1],[0, 1]]
for n in range(N):
maps.append(list(sys.stdin.readline()))
for n in range(N):
for m in range(M):
maps[n][m] = 0 if maps[n][m] == 'W' else 1
for n in range(N):
for m in range(M):
if maps[n][m] in [0, 1]:
target = maps[n][m]
count = 0
queue = deque()
queue.append([n, m])
maps[n][m] = -1
while len(queue) > 0:
x, y = queue.popleft()
count += 1
for i in range(4):
nx = x + delta[i][0]
ny = y + delta[i][1]
if 0 <= nx < N and 0 <= ny < M and maps[nx][ny] == target:
queue.append([nx,ny])
maps[nx][ny] = -1
count *= count
if target == 0:
W += count
else:
B += count
print(f"{W} {B}")
추석연휴가 껴 있기도 했고, 개인적인 일로 지방을 오가느라 시간이 없기도 했고.... 무엇보다 근무도 바빴고... 여러 사정이 있었지만 결국엔 제가 게을렀던 거겠죠.
Java를 하도 안쓰다 보니 (현재 하고 있는 업무에서 90% 이상 Python을 씁니다.) 다 까먹어가고 있는 느낌이라 급하게 쉬운 문제를 하나 풀어봤습니다.
정말 기본적인 bfs 문제라 딱히 설명할건 없네요. visit 체크만 잘해주면 풀리는 문제였습니다. 주의 할 점은 N과 M이 거꾸로 주어진다는 정도입니다. 예제에서 티가 안나는 부분이라(예제 입력에선 N == M입니다.) 첫 제출에서 index 범위가 넘어가는 런타임 에러를 당했네요.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class q1303_BOJ_전쟁전투 {
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int B = 0;
int W = 0;
int[][] map = new int[N][M];
Queue<int[]> queue = new LinkedList<int[]>();
for (int n = 0; n < N; n++) {
char[] line = br.readLine().toCharArray();
for (int m = 0; m < M; m++) {
map[n][m] = (line[m] == 'W') ? 0 : 1;
}
}
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
if (map[n][m] == 0 || map[n][m] == 1) {
int target = map[n][m];
int count = 0;
queue.offer(new int[] { n, m });
map[n][m] = -1;
while (!queue.isEmpty()) {
int[] now = queue.poll();
count += 1;
for (int i = 0; i < 4; i++) {
int nx = now[0] + delta[i][0];
int ny = now[1] + delta[i][1];
if (isIn(nx, ny, N, M) && map[nx][ny] == target) {
queue.offer(new int[] { nx, ny });
map[nx][ny] = -1;
}
}
}
if (target == 0) {
W += (count * count);
} else {
B += (count * count);
}
}
}
}
sb.append(W).append(" ").append(B);
System.out.println(sb);
}
private static boolean isIn(int x, int y, int n, int m) {
return 0 <= x && x < n && 0 <= y && y < m;
}
}
그리디 하게 합이 더 큰 쪽의 큐에서 수를 빼서 작은 쪽으로 넣으면 되는데, 이유는 조금만 생각해봐도 떠올릴 수 있습니다.
(큐의 선입선출 구조를 생각하시면 왜 그리디하게 풀이해서 정답이 나오는지 알 수 있습니다.)
입력된 리스트를 두개의 큐에 (Python의 경우 deque) 담고 그리디 하게 값을 빼고 넣어주며 같은 값이 되게 해 주면 됩니다.
실행시간을 단축시키는 가지치기가 몇개 가능한데, 우선 두 큐의 합을 더한 값이 홀수면 어떤 방법을 써도 같게 만들 수가 없습니다. 3을 정수로 2등분 시키는 게 불가능하듯이요.
2로 나눈 나머지가 0이 아니면 -1을 리턴하시면 됩니다. 그리고 큐의 합을 매번 구하지 않도록 초기 상태에서 합을 미리 구해놓은 다음, 옮기는 수만 합에서 직접 빼고 더해주면 매번 큐의 합을 구하는 것보다 빠르게 동작할 수 있습니다.
from collections import deque
def solution(queue1, queue2):
left = sum(queue1)
lqueue = deque(queue1)
right = sum(queue2)
rqueue = deque(queue2)
limit = 2 * (len(queue1) + len(queue2))
count = 0
if (left + right) % 2 == 1:
return -1
while count < limit:
if left == right:
return count
if left < right:
gap = rqueue.popleft()
left += gap
right -= gap
lqueue.append(gap)
else:
gap = lqueue.popleft()
right += gap
left -= gap
rqueue.append(gap)
count += 1
return -1
print(solution([3, 2, 7, 2], [4, 6, 5, 1]))