BJ S2 21736 헌내기는 친구가 필요해 - Java

[문제링크]

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

---

[문제]

2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다. 

도연이가 다니는 대학의 캠퍼스는 N×M$N \times M$ 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가 (x$x$, y$y$)에 있다면 이동할 수 있는 곳은 (x+1$x+1$, y$y$), (x$x$, y+1$y+1$), (x−1$x-1$, y$y$), (x$x$, y−1$y-1$)이다. 단, 캠퍼스의 밖으로 이동할 수는 없다.

불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해보자.

---

[입력]

첫째 줄에는 캠퍼스의 크기를 나타내는 두 정수 N$N$ (1≤N≤600$ 1 \leq N \leq 600$), M$M$ (1≤M≤600$ 1 \leq M \leq 600$)이 주어진다.

둘째 줄부터 N$N$개의 줄에는 캠퍼스의 정보들이 주어진다. O는 빈 공간, X는 벽, I는 도연이, P는 사람이다. I가 한 번만 주어짐이 보장된다.

---

[출력]

첫째 줄에 도연이가 만날 수 있는 사람의 수를 출력한다. 단, 아무도 만나지 못한 경우 TT를 출력한다.

---

[예제 입력 1]

3 5
OOOPO
OIOOX
OOOXP

---

[예제 출력 1]

1

 

---

[예제 입력 2]

3 3
IOX
OXP
XPP

---

[예제 출력 2]

TT

 

[설명]

이 문제도 기본적인 BFS문제로 보인다.공간인지, 사람인지, 벽인지를 판단하여 사람을 만나게 되면 +1을 해주고,
친구를 만들 수 없다면 TT를 출력해주면 된다.

 

 

백준 알고리즘 21736번 JAVA풀이

 

import java.util.*;
public class BJ21736 {
    public static int[][] arr;
    public static boolean[][] visited;
    private static int[] dr = {-1,0,1,0};
    private static int[] dc = {0,1,0,-1};
    private static int answer = 0;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(" ");
        int r = Integer.parseInt(s[0]);
        int c = Integer.parseInt(s[1]);
        arr = new int[r][c];
        visited = new boolean[r][c];

        int ir=0;
        int ic=0;
        // 배열 입력 받기
        for(int i=0;i<r;i++){
            String st = sc.nextLine();
            for(int j=0;j<c;j++){
                if(st.charAt(j)=='O'){              // 공간
                    arr[i][j] = 0;
                }else if(st.charAt(j)=='I'){        // 본인
                    arr[i][j] = 1;
                    ir=i;
                    ic=j;
                }else if(st.charAt(j)=='P'){        // 사람
                    arr[i][j] = 2;
                }else if(st.charAt(j)=='X'){        // 벽
                    arr[i][j] = 3;
                }
            }
        }



        Queue<Node> q = new LinkedList<>();
        q.add(new Node(ir,ic));
        visited[ir][ic]=true;

        while(!q.isEmpty()){
            for(int i=0;i<q.size();i++) {
                Node n = q.poll();
                for(int d=0;d<4;d++){
                    int nr = n.r + dr[d];
                    int nc = n.c + dc[d];

                    if(isChecked(nr,nc, r, c)){
                        if(!visited[nr][nc]){
                            if(arr[nr][nc]==0) {
                                q.add(new Node(nr, nc));
                                visited[nr][nc]=true;
                            }
                            if(arr[nr][nc]==2){
                                q.add(new Node(nr, nc));
                                answer++;
                                arr[nr][nc]=0;
                                visited[nr][nc]=true;
                            }
                        }
                    }
                }
            }
        }
        if(answer!=0) {
            System.out.println(answer);
        }else {
            System.out.println("TT");
        }
    }
    public static boolean isChecked(int nr, int nc, int r, int c){
        return nr>=0 && nc>=0 && nr<r && nc<c;
    }
    public static class Node{
        int r;
        int c;

        public Node(int r, int c){
            this.r=r;
            this.c=c;
        }
    }
}

 

 

 

궁금하신 부분이나 부족한 점은 댓글로 알려주시면 감사하겠습니다.