[BAEKJOON]21736 헌내기는 친구가 필요해

문제 요약

• 알고리즘 분류: bfs, 구현, 시물레이션
• 난이도: Silver2
• 문제내용:
  • 가로, 세로 크기가 n, m인 캠퍼스 공간이 있다.
  • 그림영역과 빈 영역이 있는데 그림 영역 개수와 가장 큰 그림을 출력해라.
• 사이트: https://www.acmicpc.net/problem/21736

21736번: 헌내기는 친구가 필요해

문제풀이

 이번 문제는 DFS,BFS 탐색 문제이다. DFS로 풀수있지만 BFS가 DFS보다 속도가 더 빨라서 이번 문제는 BFS로 푸는게 좋다.  BFS 탐색 알고리즘에 관한 자세한 설명은 여기에서 확인 해보면 알 수 있다.

 기존 BFS는 각 노드간의 탐색인데 이번에는 2차원 배열로 응용한 BFS 탐색이다. 노드 대신 2차원 배열로 변경 된것만 생각하면 된다.

 

문제 접근 방법

 이번 문제에서는 크게 두 개만 구현 하면된다.

1. 도연의 위치

2. BFS 탐색

 

1. 도연의 위치

 (0, 0)에서 시작하는것인 아니라 도연의 위치 부터 탐색이 시작 되기 때문에 도연의 위치 부터 찾는것 부터 구현 해야 한다.

Python

def findLocation():
    for i in range(N):
        for j in range(M):
            if campus[i][j] == 'I':
                return (i, j)

Java

int x = 0;
int y = 0;

// 시작 위치 찾기
for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
        if (campus[i][j] == 'I'){
            x = i;
            y = j;
            campus[i][j] = 'X';
            break;
        }
    }
}

 

2. BFS

 이번 문제의 핵심는 BFS + 시물레이션 2개를 구현 해야 한다. 일단 시물레이션은 어떻게 구현 해야 하는지 부터 봐야 한다.  도연의 위치 부터 시작해서 탐색 완료하면 X로 표기하고 만약에 사람을 찾으면 개수를 +1 증가 시키기만 하면된다.

Python

파이썬 지원하는 모듈에서는 queue가 없어서 deque(데크)를 사용 해서 queue로 구현 해야한다. queue는 pip에 따로 install을 받으면되지만 실제 코딩테스트에서는 불가능 하기 때문에 deque로 사용 해야한다.

queue = deque()
queue.append((x, y))

count = 0

while queue:
    x, y = queue.popleft()

    for k in range(4):
        fx, fy = x + dx[k], y + dy[k]
        if (0 <= fx < N and 0 <= fy < M) and campus[fx][fy] != 'X':
            # 사람일 경우
            if campus[fx][fy] == 'P':
                count += 1
            campus[fx][fy] = 'X'
            queue.append((fx, fy))

Java

자바에서는 Queue라는 모듈을 제공하기 때문에 queue를 따로 구현하지 말고 Queue 모듈을 사용하면된다.

Queue<int []> queue = new LinkedList<>();
queue.add(new int[] {x, y});
int[] location;
int fx, fy;
int count = 0;

//bfs 탐색 시작
while (queue.size() > 0){
    location = queue.poll();
    x = location[0];
    y = location[1];

    for(int k = 0; k < 4; k++){
        fx = x + dx[k];
        fy = y + dy[k];
        if((fx >= 0 && fx < n && fy >= 0 && fy < m) && campus[fx][fy] != 'X'){
            // 사람일 경우
            if (campus[fx][fy] == 'P'){
                count++;
            }
            campus[fx][fy] = 'X';
            queue.add(new int[] {fx, fy});
        }
    }

}

Code

python

import sys
from collections import deque

input = sys.stdin.readline

# 도연 위치 찾기
def findLocation():
    for i in range(N):
        for j in range(M):
            if campus[i][j] == 'I':
                return (i, j)

def bfs():
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    x, y = findLocation()
    
    # 도연 위치는 탐색 안하는 곳으로 설정 한다.
    campus[x][y] = 'X'

    queue = deque()
    queue.append((x, y))

    count = 0
    
    while queue:
        x, y = queue.popleft()
        
        for k in range(4):
            fx, fy = x + dx[k], y + dy[k]
            if (0 <= fx < N and 0 <= fy < M) and campus[fx][fy] != 'X':
                # 사람일 경우
                if campus[fx][fy] == 'P':
                    count += 1
                campus[fx][fy] = 'X'
                queue.append((fx, fy))

    return count

N, M = map(int, input().split())

campus = [list(input())  for _ in range(N)]

count = bfs()

print("TT" if count == 0 else count)

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static int n, m;
	static char[][] campus;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		campus = new char[n][m];

		for(int i = 0; i < n; i++){
			campus[i] = br.readLine().toCharArray();
		}

		int count = bfs();

		System.out.println(count == 0? "TT" : count);

	}

	public static int bfs(){

		int[] dx = {0, 0, -1, 1};
		int[] dy = {-1, 1, 0, 0};


		int x = 0;
		int y = 0;

		// 시작 위치 찾기
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if (campus[i][j] == 'I'){
					x = i;
					y = j;
					campus[i][j] = 'X';
					break;
				}
			}
		}

		Queue<int []> queue = new LinkedList<>();
		queue.add(new int[] {x, y});
		int[] location;
		int fx, fy;
		int count = 0;

		//bfs 탐색 시작
		while (queue.size() > 0){
			location = queue.poll();
			x = location[0];
			y = location[1];

			for(int k = 0; k < 4; k++){
				fx = x + dx[k];
				fy = y + dy[k];
				if((fx >= 0 && fx < n && fy >= 0 && fy < m) && campus[fx][fy] != 'X'){
					// 사람일 경우
					if (campus[fx][fy] == 'P'){
						count++;
					}
					campus[fx][fy] = 'X';
					queue.add(new int[] {fx, fy});
				}
			}

		}

		return count;
	}

}