[BOJ/Java] 21736. 헌내기는 친구가 필요해

[BOJ/Java] 21736. 헌내기는 친구가 필요해

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

---

문제 해석

이 문제에서는 학교 지도에서 'I'로 표시된 시작 위치에서 출발하여 'P'로 표시된 친구들을 만나는 시뮬레이션을 수행한다. 지도는 NxM 그리드 형태로 주어지며, 탐색은 네 방향으로 이동이 가능하다. 목표는 최대한 많은 친구('P')를 만나는 것이며, 만약 하나도 만나지 못했다면 "TT"를 출력한다.

풀이 과정

1. 초기화: 입력을 받아 지도의 크기(N, M)와 각 위치의 문자를 초기화한다. 시작 위치('I')를 찾아 start 변수에 저장한다.
2. BFS 실행: 시작 위치에서 BFS를 시작하여 지도상의 모든 접근 가능한 경로를 탐색한다. 이동할 때마다 방문한 위치를 'X'로 표시하여 중복 방문을 방지한다.
3. 친구 만남 처리: 이동하는 각 위치가 'P'일 경우, ans 변수를 증가시켜 친구를 만난 횟수를 기록한다.
4. 결과 출력: 만난 친구가 없을 경우 "TT"를 출력하고, 그렇지 않으면 만난 친구의 수를 출력한다.

코드

package edu.ssafy.im.BOJ.Silver.S2.No21736;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	private static int N; // 지도의 행 수
	private static int M; // 지도의 열 수
	private static char[][] map; // 지도 정보를 담는 배열
	private static Point start; // 시작 위치를 나타내는 변수
	private static int ans; // 만난 친구의 수
	private static int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 네 방향 이동
	
	static class Point {
		int x, y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		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 row = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = row.charAt(j);
				if(map[i][j] == 'I') start = new Point(i, j); // 시작 위치 초기화
			}
		}
		
		bfs(); // BFS 탐색 실행
		
		if(ans == 0) sb.append("TT"); // 친구를 하나도 만나지 못한 경우
		else sb.append(ans); // 만난 친구의 수 출력
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
	
	private static void bfs() {
		Queue<Point> q = new ArrayDeque<>();
		q.offer(start);
		map[start.x][start.y] = 'X'; // 시작 위치 방문 처리
		
		while(!q.isEmpty()) {
			Point p = q.poll();
			for(int[] d: direction) {
				int nx = p.x + d[0];
				int ny = p.y + d[1];
				
				if (nx < 0 || ny < 0 || nx >= N || ny >= M || map[nx][ny] == 'X') continue; // 이동 가능한지 확인
				if (map[nx][ny] == 'P') ans++; // 친구를 만난 경우
				
				map[nx][ny] = 'X'; // 방문 처리
				q.offer(new Point(nx, ny)); // 큐에 추가
			}
		}
	}
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 모든 셀을 최대 한 번씩 방문하므로 O(NM)이다. BFS는 각 노드를 한 번씩만 처리하며, 각 노드는 최대 4번의 이동을 고려한다.

느낀점

이 문제를 통해 BFS를 사용하여 그래프 내의 모든 노드를 효율적으로 탐색하는 방법을 실습할 수 있었다. 복잡한 지도 내에서 효율적인 경로 탐색과 상태 관리의 중요성을 이해하는 좋은 기회였다. 또한, 문제의 조건을 정확히 이해하고 적절한 데이터 구조를 선택하는 것이 중요하다는 것을 배웠다.