21736_헌내기는 친구가 필요해

사용 알고리즘: bfs

사용 언어: java

 

 

 

 

 

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_bj_21736_헌내기친구 {

    static int n, m, res;
    static int Ix, Iy;
    static char[][] map;
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};

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

        map = new char[n][m];

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

                if(map[i][j]=='I'){
                    Ix = i;
                    Iy = j;
                }
            }
        } //입력

        bfs(Ix, Iy);

        if(res!=0){
            System.out.println(res);
        } else {
            System.out.println("TT");
        }
    }

    private static void bfs(int x, int y) {
        Queue<Point> q = new ArrayDeque<>();
        q.offer(new Point(x, y));
        while (!q.isEmpty()) {
            Point p = q.poll();
            for (int d = 0; d < 4; d++) {
                int nx = p.x+dx[d];
                int ny = p.y+dy[d];

                if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
                if(map[nx][ny]=='X' || map[nx][ny]=='I') continue;
                if(map[nx][ny]=='P') res++;

                q.offer(new Point(nx, ny));
                map[nx][ny] = 'I'; //방문 처리
            }
        }
    }
}

 

 

알고리즘 선택 이유:

x를 기준으로 구역 나누기 기법을 써야 하기 때문에 bfs가 가장 적합하다고 판단

 

이슈: 

무한 루프 -> 방문처리를 위해 map[nx][ny]='I'를 넣었음에도 불구하고...

 

해결:

If조건에서 map[nx][ny]=='I'를 안 넣음 => 방문 처리를 그냥 'X'로 했으면 됐지만, 도연이가 움직였다는 걸 표시하고 싶어서 I를 넣음

 

느낀점:

방문 처리 뿐 아니라, 방문된 곳의 영역을 가지 않는 조건도 잘 넣어주기!