[백준] 21736번 : 헌내기는 친구가 필요해 - JAVA

문제

https://www.acmicpc.net/problem/21736

 

 

문제 풀이

딱 BFS 기초 문제이다. 가장 중요한 건? "방문철씨" (방문처리)

 

1. Queue 에 처음 도연이의 위치를 저장한다.

더 이상 도연이의 위치를 탐색할 필요는 없으므로 방문처리를 한다.

if (board[i][j] == 'I') {
                    queue.offer(new int[]{i, j});
                    visited[i][j] = true;
                }

 

 

2. 사방탐색으로 이동할 수 있는 곳이면 Queue에 추가한다.

1) 배열을 만들어서 상하좌우 움직임을 저장한다. 그 후 0~3 인덱스를 탐방한다.

int[] dr = {0, 0, -1, 1};
int[] dc = {-1, 1, 0, 0};

 

2) 세 가지 조건 : 캠퍼스를 벗어나지 않고, 방문한적이 없고, 'X' 벽이 아닌 (즉, 이동할 수 있는 곳)

if (0 <= nr && nr < N && 0 <= nc && nc < M && !visited[nr][nc] && board[nr][nc] != 'X')

 

3) 더 이상 탐색할 필요가 없으니 Queue에 넣어준 후에는 가장 중요한 방문처리를 해준다.

visited[i][j] = true;

 

   

3. 친구가 0이면 “TT” 처리를 해준다.

if (ans == 0)
	System.out.println("TT");
else
    System.out.print(ans);

 

전체 코드

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

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); // 1~600 세로
        int M = Integer.parseInt(st.nextToken()); // 1~600 가로

        int[] dr = {0, 0, -1, 1};
        int[] dc = {-1, 1, 0, 0};

        char[][] board = new char[N][M];
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            board[i] = (br.readLine()).toCharArray();
            for (int j = 0; j < M; j++) {
                if (board[i][j] == 'I') {
                    queue.offer(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }

        int ans = 0;


        while (!queue.isEmpty()) {

            int[] arr = queue.poll();

            int r = arr[0];
            int c = arr[1];

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (0 <= nr && nr < N && 0 <= nc && nc < M && !visited[nr][nc] && board[nr][nc] != 'X') {
                    queue.offer(new int[]{nr, nc});
                    visited[nr][nc] = true;
                    if (board[nr][nc] == 'P') {
                        ans++;
                    }
                }
            }
        }

        if (ans == 0)
            System.out.println("TT");
        else
            System.out.print(ans);


        br.close();
    } // main
} // class

 

BFS는 한 번 이해하고 나면 다른 비슷한 유형의 문제에서도 쉽게 접근하고 풀 수 있다.