[백준 알고리즘] 백준 21736번 헌내기는 친구가 필요해 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 21736번 헌내기는 친구가 필요해 자바(Java)

1) 문제번호 : 21736번

 

2) 문제 출처

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

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

 

2. 문제

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

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

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

 

3. 제약사항

- 

4. 입력

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

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

 

5. 출력

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

 

6. 풀이

- DFS나 BFS의 기본적인 문제다.

- Python으로 풀려고 했는데, 재귀 문제를 해결하지 못해 자바로 풀었다.

- 도연이의 위치인 I를 입력받으면 위치를 저장해놓고, DFS를 돌린다.

- 4방 탐색을 하여 벽이 아니라면 이동해서 P가 나오면 만난 사람의 수를 증가시켜 준다.

 

7. 소스 코드

import java.util.*;

public class Main {
	static int N; // 캠퍼스 크기 가로
	static int M; // 캠퍼스 크기 세로
	
	static char[][] campus; // 캠퍼스
	static boolean[][] visit; // 방문체크
	
	static int[] dx = {-1, 1, 0, 0}; // 상하좌우
	static int[] dy = {0, 0, -1, 1}; // 상하좌우
	
	static int result = 0; // 만나는 사람 수
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); // 캠퍼스 크기 가로
		M = sc.nextInt(); // 캠퍼스 크기 세로
		
		campus = new char[N][M]; // 캠퍼스 
		visit = new boolean[N][M]; // 방문체크
		
		//도연이 위치 저장 변수
		int r = 0;
		int c = 0;
		
		//캠퍼스 입력
		for(int i=0;i<N;i++) {
			String s = sc.next();
			for(int j=0;j<M;j++) {
				campus[i][j] = s.charAt(j);
				//도연이 위치가 있으면 저장
				if(campus[i][j]=='I') {
					r = i;
					c = j;
				}
			}
		}
		
		//DFS 시작
		DFS(r,c);
		
		//만난 사람이 없으면 TT 출력
		if(result==0) System.out.println("TT");
		// 만난 사람이 있으면 result 출력
		else System.out.println(result);
		
	}
	
	public static void DFS(int x, int y) {
		visit[x][y] = true;
		
		if(campus[x][y]=='P') result++;
		
		for(int i=0;i<4;i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx>=0 && ny >=0 && nx<N && ny<M && !visit[nx][ny]) {
				if(campus[nx][ny]!='X') {
					DFS(nx,ny);
				}
			}
		}
	}
}

 

---