[JAVA][BOJ][S2] 21736. 헌내기는 친구가 필요해

21736번: 헌내기는 친구가 필요해

문제

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

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

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

입력

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

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

출력

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

풀이

dfs를 통해 풀어 봤다 처음 배열에 값을 넣을 때 도연이의 위치(I)를 찾아 그 값을 저장해 두고, dfs를 도연이의 위치부터 돌리면 된다 O나 P를 만나면 앞으로 갈 수 있고, X는 벽이기 때문에 지나가지 못한다 친구의 수가 0명이면 TT를 출력하고 아니라면 친구의 수를 출력했다

코드

package 문제풀이;

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

public class S2_21736_헌내기는친구가필요해 {
	static int N, M, cnt;
	static char[][] arr;
	static boolean[][] visited;
	static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, 1, -1};

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		arr = new char[N][M];
		visited = new boolean[N][M];
		
		int x = 0;
		int y = 0;
		
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < M; j++) {
				arr[i][j] = str.charAt(j);
				if(arr[i][j] == 'I') {
					x = i;
					y = j;
				}
			}
		}
		
		dfs(x, y);
		
		if(cnt == 0) System.out.println("TT");
		else System.out.println(cnt);

	}

	private static void dfs(int x, int y) {
		visited[x][y] = true;
		
		if(arr[x][y] == 'P') {
			cnt++;
		}
		for (int k = 0; k < 4; k++) {
			int i = x + dx[k];
			int j = y + dy[k];
			if(i<0 || i>=N || j<0 || j>=M || visited[i][j] || arr[i][j] == 'X') continue;
			dfs(i, j);
		}
		
	}

}

결과

 

#자바 #java #boj #백준 #알고리즘