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

➡️문제 링크

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

 

💡아이디어

캠퍼스는 N*M 크기, 이동하는 방법은 벽이 아닌 상하좌우,  이동할 수 있는 곳은 (x+1, y), (x, y+1), (x-1, y), (x, y-1)

문제를 읽으니 자동적으로 "그래프"문제다! 라고 판단했다

 

 

✏️문제 풀이

1. BFS - 성공

2차원 배열로 캠퍼스 정보를 입력받고 BFS를 실행한다.

이때 주의할 점이 있다면,

사방탐색 후 해당 위치를 방문할 수 있는지 판단할 때 "I"의 위치도 접근할 수 있어야 한다.

처음에는 O(빈 공간) && 사람(P)이 위치한 곳만 접근 가능할게 해야지 했다가, 다시 생각해보니

!= X(벽) 만 아니면 다 접근 가능했었다

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

public class Main {
	static int N, M;
	static char [][] map;
	static int [] dx = {-1, 0, 1, 0};
	static int [] dy = {0, 1, 0, -1};
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		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];
		int sx = 0;	// 도연 초기위치
		int sy = 0;
		for(int i = 0; i < N; i++) {
			String str = br.readLine();
			for(int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j);
				if(map[i][j] == 'I') {
					sx = i;			// 도연 초기 위치
					sy = j;
				}
			}
		}
		
		// bfs 탐색 돌리기
        int result = bfs(sx, sy);
		if(result == 0) {
			System.out.println("TT");
		}else {
			System.out.println(result);			
		}

	}
	
	static int bfs(int x, int y) {
		Queue<int []> que = new LinkedList<>();
		boolean [][] visited = new boolean[N][M];	// 방문 확인 배열
		int count = 0;	// 만난 사람 수
		
		que.add(new int [] {x, y});
		visited[x][y] = true;
		
		while(!que.isEmpty()) {
			int [] curPoint = que.poll();
			
			for(int i = 0; i < 4; i++) {
				int tx = dx[i] + curPoint[0];		// 현재 위치로 사방탐색 
				int ty = dy[i] + curPoint[1];
			
				// 범위 탐색
				if(isRange(tx, ty) && !visited[tx][ty]) {
					if(map[tx][ty] != 'X') {
						if(map[tx][ty] == 'P') count++;
						
						// 방문처리 및 확장
						visited[tx][ty] = true;
						que.add(new int[] {tx, ty});
					}
				}
			}
			
		}
		
		return count;
	}
	
	static boolean isRange(int x, int y) {
		return x >= 0 && x < N && y >= 0 && y < M;
	}

}

 

 

 

+) 

처음 BFS 로 풀었을 때 내 생각보다 시간이 좀 걸렸다

그래서 다른 사람들의 풀이를 보며 DFS가 더 빠른건가? 싶었는데 

DFS로 풀고 글을 쓰기 위해

다시 내 코드를 보니 BFS를 실행한 후 답을 판별하는 과정에서

0이 아닌 경우,

답을 출력하기 위해 또 한 번 BFS를 출력하는게 원인이라는 걸 알았다

// bfs 탐색 돌리기
if(bfs(sx, sy) == 0) {
	System.out.println("TT");
}else {
	System.out.println(bfs(sx, sy));			
}

 

어쩐지 오래 걸리더라!

 

 

2. DFS - 성공

다른 사람들의 풀이를 보니 DFS로 많이 풀어 나도 다시 풀어봤다.

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

public class Main {
	static int N, M;
	static char [][] map;
	static int [] dx = {-1, 0, 1, 0};
	static int [] dy = {0, 1, 0, -1};
    static int count = 0;
    static boolean [][] visited;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		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];
        visited = new boolean[N][M];	// 방문 확인 배열
		int sx = 0;	// 도연 초기위치
		int sy = 0;
		for(int i = 0; i < N; i++) {
			String str = br.readLine();
			for(int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j);
				if(map[i][j] == 'I') {
					sx = i;			// 도연 초기 위치
					sy = j;
				}
			}
		}
		
		// bfs 탐색 돌리기
        dfs(sx, sy);
		if(count == 0) {
			System.out.println("TT");
		}else {
			System.out.println(count);			
		}

	}
	
	static void dfs(int x, int y) {
        visited[x][y] = true;
        if(map[x][y] == 'P') count++;

		for(int i = 0; i < 4; i++) {
			int tx = dx[i] + x;		// 현재 위치로 사방탐색 
			int ty = dy[i] + y;
			
			// 범위 탐색
			if(isRange(tx, ty) && !visited[tx][ty]) {
				if(map[tx][ty] != 'X'){
                    dfs(tx, ty);
                } 
			}
		}
	}
	
	static boolean isRange(int x, int y) {
		return x >= 0 && x < N && y >= 0 && y < M;
	}

}