[Algorithm/Java] 백준 21736 - 헌내기는 친구가 필요해

---

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

---

📌 문제

문제 유형

• 그래프

문제 설명

• 캠퍼스 내에서 도연이가 위치한 곳(‘I’)에서 시작해 사람(‘P’)들을 만나는 문제이다.
• 벽(‘X’)은 지나갈 수 없고, 빈 공간(‘O’)과 사람(‘P’)은 이동할 수 있다.
• 도연이가 만날 수 있는 사람의 수를 구하고, 아무도 만나지 못하면 “TT”를 출력한다.

입력

3 5
OOOPO
OIOOX
OOOXP

출력

1

🔍 문제 풀이

1. 도연이 위치부터(I) 시작
2. BFS로 탐색하면서 p를 만날 때 마다 카운트
3. 이동 가능한 좌표는 'X'가 아닌 'O', 'P'
4. 방문 처리는 큐에서 꺼낸 뒤에 현재 위치 graph[cx][cy] = 'X'로 수행
5. cnt > 0이면 사람 수 출력, 아니면 "TT" 출력

📌 놓친 점

방문 처리 위치와 방식

이 문제에서는 'P'를 정확히 세야 하므로 방문 처리를 언제, 어떻게 하느냐가 매우 중요하다.

처음엔 큐에 넣을 때 graph[nx][ny] = 'X'로 방문 마킹을 했지만,

이 경우 'P'를 확인하기도 전에 'X'로 덮어버려 cnt++가 제대로 되지 않는 문제가 발생하였다.

해결 방법 2가지

① 꺼낸 뒤 graph를 직접 수정하는 방식

• 처음 사용한 해결 방법이다.
• 큐에 넣을 때는 아무 마킹도 하지 않고, 꺼낸 후에 graph[cx][cy] = 'X'로 방문 처리한다.
• 이 방식은 'P'를 먼저 확인한 뒤 덮기 때문에 카운트 누락이 발생하지 않는다.
• 단점은 같은 좌표가 큐에 여러 번 들어갈 수 있어,
• 반드시 if (graph[cx][cy] == 'X') continue; 와 같은 중복 방문 체크가 필요하다.

if (graph[cx][cy] == 'X') continue;
if (graph[cx][cy] == 'P') cnt++;
graph[cx][cy] = 'X';

② visited 배열로만 방문 관리 (현재 사용한 방식)

• 방문 여부는 visited[x][y] 배열로만 관리하고, graph는 수정하지 않는다.
• ‘P’든 ‘O’든 ‘I’든, ‘X’가 아닌 좌표 중 처음 도달하는 좌표만 큐에 들어가고 방문 처리됨

• 이후 해당 좌표에서 꺼내는 시점에 graph[cx][cy] == 'P'이면 cnt++

• 즉,
  1. 방문한 좌표는 한 번만 큐에 들어가고 한 번만 꺼내짐 (중복 없음)
  2. visited 처리는 큐에 넣을 때 하고, graph[cx][cy] == 'P' 판단은 큐에서 꺼낼 때 하니까 ‘P’는 그대로 남아 있어서 cnt++가 가능

💻 전체 코드

package org.example;

import java.io.*;
import java.util.*;

public class Main {
    static char[][] graph;
    static boolean[][] visited;
    static int n, m, start_x, start_y;

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

    static int bfs(){
        int cnt = 0;
        Deque<int[]> dq = new ArrayDeque<>();
        dq.offer(new int[]{start_x, start_y});
        visited[start_x][start_y] = true;

        while(!dq.isEmpty()){
            int[] current = dq.poll();
            int cx = current[0];
            int cy = current[1];

            if(graph[cx][cy] == 'P') cnt++;

            for(int i=0; i<4; i++){
                int nx = dx[i] + cx;
                int ny  = dy[i] + cy;

                if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if(graph[nx][ny]!='X' && !visited[nx][ny]){
                    dq.offer(new int[]{nx,ny});
                    visited[nx][ny] = true;
                }

            }
        }
        return cnt;
    }

    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());

        graph = new char[n][m];
        visited = new boolean[n][m];

        for(int i=0; i<n; i++){
            String s = br.readLine();
            for(int j=0; j<m; j++){
                graph[i][j] = s.charAt(j);

                if(graph[i][j] == 'I'){
                    start_x = i;
                    start_y = j;
                }
            }
        }
        int result = bfs();
        if(result > 0){
            System.out.println(result);
        }else{
            System.out.println("TT");
        }

    }
}