알고리즘 분류 : 그래프 이론, 그래프 탐색
문제
전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.
N명이 뭉쳐있을 때는 N2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.
입력
첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 병사가 한 명 있다. B는 파란색, W는 흰색이다. 당신의 병사와 적국의 병사는 한 명 이상 존재한다.
출력
첫 번째 줄에 당신의 병사의 위력의 합과 적국의 병사의 위력의 합을 출력한다.
예제 입출력
접근
입력을 보게 되면 격자형그래프로 주어진다.
이 문제는 4963번(섬의 이동)과 거의 동일한 문제로 볼수 있다.
주어진 격자형 그래프의 노드를 하나씩 돌면서 bfs탐색을 하는것이다.
시작이 W이면 W인 노드만, B면B인 노드만 탐색을 하고 탐색이 끝나면 각각의 위치를 방문처리하기 위해 'C'로 둔다.
그리고 탐색할때마다 노드의 수를 세고 그 제곱을 반환한다.
접근 방법은 다음과 같다.
1. 그래프 만들기
주어진 입력을 이용해서 2차원 배열의 그래프를 만들어준다.
입력과 높이를 받고, W,B정보를 2차원 배열의 형태로 만들어주면된다.
2. bfs탐색할 노드 선정
반복문을 돌면서 시작노드를 정하게 된다.
문제에서 원하는 것은 섬처럼 병사들이 군데 군데 모여있는데, 각각의 모인 덩어리에서 병사수를 세고 이를 제곱하여 다른 덩어리들과 더한 결과를 출력하는 것이다.
이는 한 노드에서 갈수 있는 노드까지 출력하면서 수를 세고 제곱을 해주면 된다.
따라서 bfs탐색을 시작할 노드를 반복문을 돌면서 선택해주면 된다.
3. 탐색
탐색을 시작할 노드를 선정했으면 탐색을 시작하면 된다.
시작 노드가 W인지 B인지를 확인해서 그에 맞춰서 탐색을 한다.
노드를 방문할때마다 다음 탐색을 위해서 방문노드를 W,B랑 겹치지 않도록 C로 설정을 해둔다
bfs탐색이 끝나면 한 덩어리의 모여있는 병사수가 나오고, 이를 제곱해서 색깔별로 별도로 더해둔다.
더이상 탐색할 노드가 없으면 더해둔 각각의 값들을 출력해주면 된다.
import sys
from collections import deque
'''입력'''
#n:가로, m: 세로
n,m = map(int,sys.stdin.readline().split())
#그래프 생성
graph = []
for _ in range(m):
graph.append(list(sys.stdin.readline()))
#bfs 함수 정의
#start_node는 (x,y) =>(행,열)
def bfs(start_node:tuple,color:str)-> int:
count = 1
#상하좌우만 인접한 것으로 침 - 대각선 x
dx = [0,0,-1,1]
dy = [-1,1,0,0]
need_visited = deque(list())
need_visited.append(start_node)
#방문처리
graph[start_node[0]][start_node[1]] = "C"
while need_visited:
current_x,current_y = need_visited.popleft()
for i in range(4):
next_x = current_x + dx[i]
next_y = current_y + dy[i]
#그래프를 벗어나지 않고
if next_x >=0 and next_x < m and next_y >= 0 and next_y < n:
if graph[next_x][next_y] == color:
count+=1
graph[next_x][next_y] = "C"
need_visited.append((next_x,next_y))
return count
'''로직'''
#W값 누적
white_count = 0
#B값 누적
blue_count = 0
#반복문을 이용해서 시작노드를 찾음
for i in range(m):
for j in range(n):
#C이면 방문한곳
if graph[i][j] =="W":
result = bfs((i,j),"W")
white_count += result*result
elif graph[i][j] == "B":
result = bfs((i,j),"B")
blue_count += result*result
print(white_count,blue_count)결과
