문제
코드
# https://www.acmicpc.net/problem/1303
# boj, 1303: 전쟁 - 전투, Python3
from collections import deque
# 이동방향 정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# BFS (너비 우선 탐색) 알고리즘
def bfs(x: int, y: int) -> int:
queue = deque() # queue 자료구조 선언
queue.append([x, y])
visited[x][y] = True # 현재 위치 방문처리
cnt = 1 # 병사 수를 담은 변수
while queue: # queue가 빌 때 까지 무한반복
x, y = queue.popleft()
for i in range(4): # 상, 하, 좌, 우 방향 체크
nx = x + dx[i]
ny = y + dy[i]
# 주어진 범위를 벗어나지않고, 첫 방문인 경우, 같은 색 옷 병사인 경우
if 0 <= nx < m and 0 <= ny < n and visited[nx][ny] == False and colors[x][y] == colors[nx][ny]:
queue.append([nx, ny])
visited[nx][ny] = True # 현재 위치 방문처리
cnt += 1
return cnt # 병사 수 반환
if __name__ == '__main__':
n, m = map(int, input().split()) # 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다.
# 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다.
colors = [list(str(input())) for _ in range(m)]
visited = [[False] * n for _ in range(m)] # 방문처리를 담은 list
w_count, b_count = 0, 0 # 흰색 옷 병사 수, 파란색 옷 병사 수
for y in range(m):
for x in range(n):
if not visited[y][x]: # 현재 위치가 첫 방문인 경우에만 탐색 수행
cnt = bfs(y, x) # 탐색 수행 결과로 얻은 병사 수 저장
if colors[y][x] == 'W': # 현재 탐색 수행 위치가 흰색 옷 병사이면
w_count += cnt ** 2 # 흰색 옷 병사 수 제곱배 (w_count += cnt ** 2 # 흰색 옷 병사 수 제곱배)
else:
b_count += cnt ** 2
# 첫 번째 줄에 당신의 병사의 위력의 합과 적국의 병사의 위력의 합을 출력한다.
print(w_count, b_count)결과
ChatGPT Code
from typing import List, Tuple
def dfs(x: int, y: int, color: str, visited: List[List[bool]], board: List[List[str]]) -> int:
"""
dfs 함수
:param x: 현재 위치 x좌표
:param y: 현재 위치 y좌표
:param color: 현재 위치의 병사 옷 색깔
:param visited: 방문 여부 체크를 위한 2차원 리스트
:param board: 병사들의 옷 색깔 정보를 담은 2차원 리스트
:return: 현재 위치에서 뭉쳐있는 병사의 수 반환
"""
# 현재 위치 방문 처리
visited[x][y] = True
# 뭉쳐있는 병사의 수
cnt = 1
# 현재 위치에서 상하좌우 이동하며 뭉쳐있는 병사의 수 계산
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
# 범위를 벗어나면 continue
if nx < 0 or nx >= len(board) or ny < 0 or ny >= len(board[0]):
continue
# 이미 방문한 위치거나 적군일 경우 continue
if visited[nx][ny] or board[nx][ny] != color:
continue
# dfs 수행하여 뭉쳐있는 병사의 수 누적
cnt += dfs(nx, ny, color, visited, board)
return cnt
# 입력 받기
n, m = map(int, input().split())
board = [input() for _ in range(n)]
# 방문 여부 체크를 위한 2차원 리스트
visited = [[False] * m for _ in range(n)]
# 병사들의 위력 계산
my_power, enemy_power = 0, 0
for i in range(n):
for j in range(m):
# 아직 방문하지 않은 병사 위치에서 dfs 수행
if not visited[i][j]:
cnt = dfs(i, j, board[i][j], visited, board)
# 해당 병사들의 위력 계산
if board[i][j] == 'W':
my_power += cnt ** 2
else:
enemy_power += cnt ** 2
print(my_power, enemy_power)ChatGPT 문제풀이
이 문제에서는 병사들이 상하좌우로 인접해있는 경우만을 묶어서 생각해야 하므로, bfs 알고리즘이 더 적합합니다. dfs 알고리즘은 깊이 우선 탐색으로 진행하면서 노드를 방문하므로, 상하좌우의 노드를 모두 탐색하기 전에 깊이 우선으로 탐색하다가 이전에 방문했던 노드를 다시 방문해야 할 가능성이 있습니다. 하지만 bfs 알고리즘은 너비 우선으로 탐색하므로, 상하좌우의 노드를 모두 방문한 후에 다음 단계로 넘어가므로, 이전에 방문한 노드를 다시 방문할 일이 없습니다. 따라서 bfs 알고리즘이 이 문제에서 더 효율적입니다.
출처 & 깃허브
