내일부터 추석 연휴. 행복하다! 푸하핳ㅎ
그래서 내일부터 연휴동안은 잠깐 코딩에서 손 뗄 생각.
그리고 PS가 손에 잘 잡히지 않는다. 내일부터 연휴라 마음이 붕 떠서일까?
그래서 그냥 쉬운 문제 풀이나 쓰다가 마무리를 해야겠다고 생각했다.
첫번째 쉬운 문제는 바로 이 문제!
BOJ 1303 - 전쟁 - 전투 링크
(2022.09.08 기준 S1)
(치팅 하지 마요! 고추마요! 오늘 고추마요 먹을 예정임 ㅎㅎㅎㅎ)
문제
뭉쳐있는 병사 수가 N이라면 N²의 위력을 낸다고 하면
아군과 적군의 병사 위력의 합 출력
알고리즘
뭉쳐있는 같은 종류의 병사를 탐색해야 하며, 방문 순서는 상관 없으므로 BFS, DFS 둘 다 가능하다.
풀이
전형적인 베이직한 탐색 문제이다.
BFS나 DFS나 탐색 구현 방법만 다를 뿐, 큰 틀은 같다. 그 큰 틀을 풀이해보겠다.일단 아군은 W, 적군은 B로 구분되어 있다.
그럼 전쟁터에 있는 병사 순서대로 탐색을 시작하는데, 만약 위력을 구하는 데에 쓰이지 않은 병사이면 그 병사를 기준으로 탐색을 시작한다.
대각선 기준이면 인접하지 않는 것이므로 상하좌우로 탐색해나가면 되며, 방문 전이고 기준이 되는 병사와 같은 편이면 방문 체크를 해주고 뭉쳐있는 병사 수에 1을 더해주고 그 병사로 다시 탐색을 해나간다. 이게 끝이다.탐색이 끝날 때마다, 뭉쳐있는 병사 수를 제곱하여 그 병사들의 국가 위력에 더하고
모든 탐색이 끝나면 아군과 적군의 위력을 출력하면 된다.
주의사항
혹시 인덱스 에러가 난다면 가로 크기가 N, 세로 크기가 M이란 것을 확인해보자.
행열 크기를 잘 선언해야 한다.
잘 보고 탐색을 해주자.
코드
- BFS
import sys; input = sys.stdin.readline
from collections import deque
N, M = map(int, input().split())
matrix = [input().strip() for _ in range(M + 1)]
visited = [[False] * N for _ in range(M + 1)] # 방문 체크할 행렬도 전쟁터의 크기와 똑같이 만든다.
W = B = 0
for m in range(M):
for n in range(N):
if not visited[m][n]: # 만약 방문하지 않은 위치라면
result = 1 # 뭉쳐있는 병사 수. 처음엔 1명이다.
queue = deque([(m, n)]) # 이 위치부터 BFS를 시작할 것이다.
visited[m][n] = True # 시작 위치의 병사를 이미 세었으므로 시작 위치의 방문은 True
while queue:
i, j = queue.popleft()
for ii, jj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]: # 상하좌우
# 다음 위치가 범위 안이며 방문하지 않은 위치이며 병사의 종류가 시작 위치와 같아야 한다.
if 0 <= ii < M and 0 <= jj < N and not visited[ii][jj] and matrix[m][n] == matrix[ii][jj]:
visited[ii][jj] = True # 방문 체크
result += 1 # 병사 수 증가
queue.append((ii, jj)) # 덱에 다음 위치 삽입
exec('%s += result ** 2' % matrix[m][n]) # 병사들이 속해있는 국가의 위력에 뭉쳐있는 병사 수의 제곱만큼 더해준다.
print(W, B) # 정답 출력- DFS
import sys; input = sys.stdin.readline
def dfs(i, j): # DFS
result = 0
for ii, jj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]: # 상하좌우
# 다음 위치가 범위 안이며 방문하지 않은 위치이며 병사의 종류가 시작 위치와 같아야 한다.
if 0 <= ii < M and 0 <= jj < N and not visited[ii][jj] and matrix[m][n] == matrix[ii][jj]:
visited[ii][jj] = True # 방문 체크
result += 1 # 결과에 1 더하고
result += dfs(ii, jj) # 다음 위치 DFS
return result # 결과 반환
N, M = map(int, input().split())
matrix = [input().strip() for _ in range(M + 1)]
visited = [[False] * N for _ in range(M + 1)] # 방문 체크할 행렬도 전쟁터의 크기와 똑같이 만든다.
W = B = 0
for m in range(M):
for n in range(N):
if not visited[m][n]: # 만약 방문하지 않은 위치라면
visited[m][n] = True # 방문 체크 후
result = 1 + dfs(m, n) # 그 위치의 1명 + DFS 결과값이 뭉쳐있는 병사 수가 된다.
exec('%s += result ** 2' % matrix[m][n]) # 병사들이 속해있는 국가의 위력에 뭉쳐있는 병사 수의 제곱만큼 더해준다.
print(W, B) # 정답 출력여담
탐색의 기본 같은 문제.
만약, 탐색을 많이 접하지 않았다면 많이 풀면서 익숙해져야 좋을 것이다.
탐색이 정말 기본적인 알고리즘이기 때문.
(근데 난 DFS에는 마음이 잘 안가.. BFS가 편해)
