[Baekjoon] 1303_전쟁 - 전투

Silver I

문제(출처: https://www.acmicpc.net/problem/1303)

---

<전쟁-전투>

문제 

 

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

N명이 뭉쳐있을 때는 N2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.

 

 

입력

 

첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 병사가 한 명 있다. B는 파란색, W는 흰색이다. 당신의 병사와 적국의 병사는 한 명 이상 존재한다.

 

 

출력 

 

첫 번째 줄에 당신의 병사의 위력의 합과 적국의 병사의 위력의 합을 출력한다.

 

 

문제 풀이

   - my solution (Python)

import sys
from collections import deque

def bfs(arr, visited, start, find):
    dx=[-1,1,0,0] # 상하좌우
    dy=[0,0,-1,1]

    queue=deque([start])
    visited[start[0]][start[1]]=1
    cnt=1

    while queue:
        temp=queue.popleft()
        for i in range(4):
            x=temp[0]+dx[i]
            y=temp[1]+dy[i]
            if 0<=x<len(arr) and 0<=y<len(arr[0]):
                if arr[x][y]==find and visited[x][y]==0:
                    visited[x][y]=1
                    queue.append([x,y])
                    cnt+=1
    return cnt


if __name__=='__main__':
    n,m=map(int,sys.stdin.readline().split()) # 가로, 세로

    arr=[]
    for i in range(m):
        arr.append(list(sys.stdin.readline().strip()))

    visited_w=[[0]*n for i in range(m)]
    visited_b = [[0] * n for i in range(m)]
    w_cnt=0
    b_cnt=0
    for i in range(m):
        for j in range(n):
            if arr[i][j]=='W' and visited_w[i][j]==0:
                cnt=bfs(arr, visited_w, [i,j], 'W')
                w_cnt+=(cnt**2)
            elif arr[i][j]=='B' and visited_b[i][j]==0:
                cnt=bfs(arr, visited_b, [i,j], 'B')
                b_cnt+=(cnt**2)


    print(w_cnt, end=' ')
    print(b_cnt)

 

- my solution (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class _1303_전쟁_전투 {
	static int bfs(String[][] arr, int[][] visited, int[] start, String find) {
		int dx[]= {-1,1,0,0}; // 상하좌우
		int dy[]= {0,0,-1,1};
		
		visited[start[0]][start[1]]=1;
		Queue<int[]> queue=new LinkedList<>();
		queue.add(start);
		
		int cnt=1;
		
		while(queue.size()!=0) {
			int temp[]=queue.poll();
			for(int i=0; i<4; i++) {
				int x=temp[0]+dx[i];
				int y=temp[1]+dy[i];
				if(x>=0 && x<arr.length && y>=0 && y<arr[0].length) { // 범위 안
					if(arr[x][y].equals(find) && visited[x][y]==0) {
						visited[x][y]=1;
						queue.add(new int[] {x,y});
						cnt+=1;
					}
				}
			}
		}
		return cnt;
	}

	public static void main(String[] args) throws IOException{
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		
		String s=bf.readLine();
		int n=Integer.parseInt(s.split(" ")[0]); // 가로
		int m=Integer.parseInt(s.split(" ")[1]); // 세로
		
		String arr[][]=new String[m][n];
		for(int i=0; i<m; i++) {
			s=bf.readLine();
			for(int j=0; j<n; j++) {
				arr[i][j]=s.split("")[j];
			}
		}
		
		int visited_w[][]=new int[m][n]; // 방문 여부
		int visited_b[][]=new int[m][n];
		int cnt_w=0;
		int cnt_b=0;
		
		for(int i=0; i<m; i++) {
			for(int j=0; j<n; j++) {
				if(arr[i][j].equals("W") && visited_w[i][j]==0) {
					int cnt=bfs(arr, visited_w, new int[] {i,j}, "W");
					cnt_w+=(cnt*cnt);
				}
				if(arr[i][j].equals("B") && visited_b[i][j]==0) {
					int cnt=bfs(arr, visited_b, new int[] {i,j}, "B");
					cnt_b+=(cnt*cnt);
				}
			}
		}
		System.out.println(cnt_w +" "+ cnt_b);

	}

}

 

 

상하좌우를 확인하여 자신과 같은 팀이라면 몇 명인지 구한 후 N 제곱을 더해줍니다. 

 

 

• bfs ( 입력 정보, 방문 여부, 시작 위치, 찾는 값 'W' or 'B' )
  : 상하좌우를 탐색하여 현재 위치의 값과 같은 값이라면 cnt를 증가시켜주며 계속해서 탐색해줍니다.
• Main
  : 가로, 세로 입력
  : arr 정보 입력
  : visited_w, visited_b = 방문 여부
  : w_cnt, b_cnt = 병사의 위력
  : arr 전체를 순환하며 'W'일 때와 'B'일 때 bfs 탐색
  -> 반환 값 = 뭉쳐 있는 수 이므로 각 cnt에 제곱한 값을 더함
  : w_cnt, b_cnt 출력

 

 

❓ 런타임 에러?

문제에서 가로, 세로 순으로 입력받았는데 처음에 코드 작성 시 세로, 가로로 활용했기 때문에 인덱스 에러가 발생하였다.

 

---

생각🤔

 

BFS를 사용하여 쉽게 구할 수 있는 문제였다.

 

---