[백준 21736] 헌내기는 친구가 필요해 (S2)

📍 문제

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

 

📍 문제 풀이

우선 이동할 수 있는 방향은 문제에서 정해줬기 때문에 이를 `dx`, `dy` 배열에 담는다.

그리고 캠퍼스의 정보를 담을 `maps` 배열과, 도연이가 해당 지점을 방문했는지 여부를 담을 `visited` 배열의 값을 초기화해준다.

이때, 도연이는 `(0,0)`에서 탐색을 시작하는게 아니라 `I` 인 지점에서 시작하기 때문에 탐색 시작 값의 좌표를 따로 저장해준다.

 

도연이가 이동하면서 아래의 과정을 거치게된다.

1. 현재 위치에 대해서 방문처리

2. 현재 위치에 사람이 있는가? 있으면 결과값 + 1

3. 다음 갈 위치들에 대한 조건 확인

• 캠퍼스 범위 내에 존재하는가?
• 벽이 아닌가? 
• 이미 방문한 곳이 아닌가?

4. 위의 조건을 만족하는 곳이라면 현재 위치를 옮겨 다시 탐색

 

즉, 재귀의 과정을 거치게된다. 

최종적으로 만나는 사람의 수를 담아둔 `meetingPerson`의 값이 0이라면 아무도 못 만난 것이기 때문에 `TT`를 출력하고, 0이 아니라면 해당 값을 출력한다.

 

📍전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_21736 {
	static int n, m, meetingPerson = 0;
	static char[][] maps;
	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0, 1, 0, -1};
	static boolean[][] visited;

	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());
		maps = new char[n][m];
		visited = new boolean[n][m];

		int start_x = 0, start_y = 0;
		for (int i = 0; i < n; i++) {
			String str = br.readLine();
			for (int j = 0; j < m; j++) {
				maps[i][j] = str.charAt(j);

				if (maps[i][j] == 'I') {// 도연이의 초기 위치
					start_x = i;
					start_y = j;
				}
			}
		}
		dfs(start_x, start_y);
		System.out.println(meetingPerson == 0 ? "TT" : meetingPerson);

	}

	private static void dfs(int x, int y) {
		visited[x][y] = true;

		if (maps[x][y] == 'P') {
			meetingPerson++;
		}

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

			if(nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny] || maps[nx][ny] == 'X') continue;
			// 범위내에 있는 방문하지 않은 지점
			dfs(nx, ny);
		}
	}

}