💡문제 분석 요약
- 구역별로 병사들이 몇명 있는지 구한다. 해당 구역 내에 병사들의 power는 병사들 수의 제곱이다.
- white, blue 각각의 power를 구한다.
💡알고리즘 설계
- DFS, BFS 둘 다 가능하다.
- 상하좌우 체크와, 병사들 수 체크만 잘 하면 된다. 병사들 총 수는 DFS 실행횟수와 같다.
💡코드
import sys
sys.setrecursionlimit(10**6)
# 가로, 세로 "길이"가 n, m임. 즉 행:m , 열:n
n, m = map(int, input().split()) # 가로가 열 개수, 세로가 행 개수라는 것을 헷갈리면 안됨 !!!!!!!!!!!!!!!!!!!!!!!!!!
war = [list(input()) for _ in range(m)] # 여기서도 range(n)이 아니라 m임.
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# white, blue 병사들 총 수
white = 0
blue = 0
"""
1. 방문한 곳 재방문 안하기 위한 처리
2. 상하좌우 접근 가능한지 체크 & 가야하는 곳인지 체크 (ex. 값이 1이거나, 여기서처럼 아군이거나 등)
3. 해당 위치로 이동, 새로운 DFS 매개변수 설정 (ex. 병사 수 1명 늘리기, color 넘겨주기 등)
"""
def find_soldiers(x, y, soldier, color):
war[x][y] = 0 # 해당 위치는 이제 탐색 안하기 위해 0으로 바꿈
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if (0 <= nx < m and 0 <= ny < n) and (war[nx][ny] == color): # 상하좌우가 접근범위 내에 있고 and 아군이라면(같은 색이라면)
soldier = find_soldiers(nx, ny, soldier + 1, color) # 해당 위치로 이동 & 병사 수 1명 늘려줌
return soldier # dfs 탐색 끝나면 지금껏 탐색한 병사들의 총 수를 리턴
for i in range(m):
for j in range(n):
if (war[i][j] == 'W'):
white += (find_soldiers(i, j, 1, 'W')) ** 2 # 리턴값이 한 영역의 병사들 총 수니까 바로 제곱해서 합쳐줌
elif (war[i][j] == 'B'):
blue += (find_soldiers(i, j, 1, 'B')) ** 2
print(white, blue)
💡시간복잡도
- 모든 곳을 for문으로 방문하므로 O(m*n)
💡 틀린 이유
- 가로n, 세로m으로 썼는데 사실 이게 행열로 따지면 가로가 5개 있다는 게 "열이 5개"라는 소리고, 세로가 7개라는 것은 "행이 7개"라는 소리다. 즉, 가로 길이 열, 세로 길이가 행이라는 것을 알아야한다. (매우 매우 중요, 이거 인지 못해서 계속 틀림) -> 그래서 for문 돌릴 때도 m이 먼저 돌아가는 것.
💡 틀린 부분 수정 or 다른 풀이
- 가로 n을 y좌표와 비교하고, 세로 m은 x좌표와 비교한다.
💡 느낀점 or 기억할정보
- 행과 열 파악 잘하기.
반응형
'알고리즘 > 코테 스터디 (2024)' 카테고리의 다른 글
프로그래머스 - 괄호 회전 (핵심 : 회전코드 이해) (0) | 2024.09.20 |
---|---|
프로그래머스 - 방문 길이 (핵심 : line 체크) (0) | 2024.09.11 |
1789 수들의 합 (0) | 2024.08.13 |
12845 모두의 마블 (0) | 2024.08.03 |
1495 기타리스트 (0) | 2024.08.02 |