입력으로 가로 세로 크기를 받고 그 다음 입력으로는 캠퍼스의 지도를 받게 되는데 I는 시작 위치, O는 움직일 수 있는 칸, P는 사람, X는 지나갈 수 없는 칸이고 I에서 최대한 이동해봤을 때 만날 수 있는 모든 사람 수를 출력하거나 한 명도 만나지 못했다면 TT를 출력해주면 된다
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static char[][] map;
static String ans;
static int count = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] size = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
map = new char[size[0]][size[1]];
int[] start = new int[2];
for (int i = 0; i < size[0]; i++) {
String s = br.readLine();
for (int j = 0; j < size[1]; j++) {
if (s.charAt(j) == 'I') {
start[0] = i;
start[1] = j;
}
map[i][j] = s.charAt(j);
}
}
boolean[][] visited = new boolean[size[0]][size[1]];
dfs(start[0], start[1], visited);
if (count > 0) {
System.out.println(ans);
} else {
System.out.println("TT");
}
}
public static void dfs(int i, int j, boolean[][] visited) {
visited[i][j] = true;
if (map[i][j] == 'P') {
count = count + 1;
ans = String.valueOf(count);
}
// 동서남북
if (i + 1 < map.length) {
if (map[i + 1][j] != 'X' && !visited[i + 1][j]) {
dfs(i + 1, j, visited);
}
}
if (i - 1 > -1) {
if (map[i - 1][j] != 'X' && !visited[i - 1][j]) {
dfs(i - 1, j, visited);
}
}
if (j + 1 < map[0].length) {
if (map[i][j + 1] != 'X' && !visited[i][j + 1]) {
dfs(i, j + 1, visited);
}
}
if (j - 1 > -1) {
if (map[i][j - 1] != 'X' && !visited[i][j - 1]) {
dfs(i, j - 1, visited);
}
}
}
}
문제 풀이는 I에서 시작해서 X가 아닌 모든 밟을 수 있는 영역을 이동해보면 되므로 DFS를 사용해서 풀면 되는데, 동서남북으로 한칸씩 이동해서 X가 아닌 칸은 모두 이동해보되
이동한 위치가 P면 변수에 +1씩 해주는 방식으로 모든 영역을 돌고 나면, 찾은 P가 있을 경우 P의 갯수를, 찾은 P가 없었을 경우에는 TT를 출력해주면 된다
Leave a Reply