반응형
문제
https://www.acmicpc.net/problem/21736

코드
import java.io.*;
import java.util.StringTokenizer;
public class bj_21736 {
private static int N;
private static int M;
private static char[][] graph;
private static boolean[][] visited;
private static int[] dx = {1, 0, -1, 0};
private static int[] dy = {0, 1, 0, -1};
private static int result = 0;
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());
graph = new char[N][M];
visited = new boolean[N][M];
int startX = 0;
int startY = 0;
for (int i = 0; i < N; i++) {
String line = br.readLine();
for (int j = 0; j < M; j++) {
char ch = line.charAt(j);
graph[i][j] = ch;
if (ch == 'I') {
startX = i;
startY = j;
}
}
}
dfs(startX, startY);
System.out.println(result == 0 ? "TT" : result);
}
private static void dfs(int x, int y) {
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (isValid(nx, ny) && !visited[nx][ny] && (graph[nx][ny] != 'X')) {
if (graph[nx][ny] == 'P') {
result++;
}
dfs(nx, ny);
}
}
}
private static boolean isValid(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < M;
}
}
풀이
for (int i = 0; i < N; i++) {
String line = br.readLine();
for (int j = 0; j < M; j++) {
char ch = line.charAt(j);
graph[i][j] = ch;
if (ch == 'I') {
startX = i;
startY = j;
}
}
}
- 현재 문자가 `I`이면, 해당 좌표를 `startX`와 `startY`에 저장한다. (도연의 위치)
private static void dfs(int x, int y) {
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (isValid(nx, ny) && !visited[nx][ny] && (graph[nx][ny] != 'X')) {
if (graph[nx][ny] == 'P') {
result++;
}
dfs(nx, ny);
}
}
}
private static boolean isValid(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < M;
}
문제를 보면, 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이라고 한다. 따라서 이동을 할 때는 아래의 조건을 충족해야 한다.
- `isValid`: 주어진 좌표가 캠퍼스의 범위에 있는지 확인
- `!visited[nx][ny]`: 방문하지 않은 경우
- `graph[nx][ny] != 'X'`: 벽이 아닌 경우
`dfs` 함수
- 현재 위치 방문 체크
- 상하좌우로 조건에 맞을 경우, DFS 탐색 계속 진행
- 해당 좌표에 `P`가 있다면 `result`를 증가시킨다.
반응형
'백준' 카테고리의 다른 글
[백준] 4949: 균형잡힌 세상 (0) | 2025.04.18 |
---|---|
[백준] 2275: 부녀회장이 될테야 (0) | 2025.04.16 |
[백준] 7662: 이중 우선순위 큐 (0) | 2025.03.25 |
[백준] 7662: 이중 우선순위 큐 (0) | 2025.03.22 |
[백준] 1697: 숨바꼭질 (1) | 2025.03.22 |
반응형
문제
https://www.acmicpc.net/problem/21736

코드
import java.io.*;
import java.util.StringTokenizer;
public class bj_21736 {
private static int N;
private static int M;
private static char[][] graph;
private static boolean[][] visited;
private static int[] dx = {1, 0, -1, 0};
private static int[] dy = {0, 1, 0, -1};
private static int result = 0;
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());
graph = new char[N][M];
visited = new boolean[N][M];
int startX = 0;
int startY = 0;
for (int i = 0; i < N; i++) {
String line = br.readLine();
for (int j = 0; j < M; j++) {
char ch = line.charAt(j);
graph[i][j] = ch;
if (ch == 'I') {
startX = i;
startY = j;
}
}
}
dfs(startX, startY);
System.out.println(result == 0 ? "TT" : result);
}
private static void dfs(int x, int y) {
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (isValid(nx, ny) && !visited[nx][ny] && (graph[nx][ny] != 'X')) {
if (graph[nx][ny] == 'P') {
result++;
}
dfs(nx, ny);
}
}
}
private static boolean isValid(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < M;
}
}
풀이
for (int i = 0; i < N; i++) {
String line = br.readLine();
for (int j = 0; j < M; j++) {
char ch = line.charAt(j);
graph[i][j] = ch;
if (ch == 'I') {
startX = i;
startY = j;
}
}
}
- 현재 문자가
I
이면, 해당 좌표를startX
와startY
에 저장한다. (도연의 위치)
private static void dfs(int x, int y) {
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (isValid(nx, ny) && !visited[nx][ny] && (graph[nx][ny] != 'X')) {
if (graph[nx][ny] == 'P') {
result++;
}
dfs(nx, ny);
}
}
}
private static boolean isValid(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < M;
}
문제를 보면, 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이라고 한다. 따라서 이동을 할 때는 아래의 조건을 충족해야 한다.
isValid
: 주어진 좌표가 캠퍼스의 범위에 있는지 확인!visited[nx][ny]
: 방문하지 않은 경우graph[nx][ny] != 'X'
: 벽이 아닌 경우
dfs
함수
- 현재 위치 방문 체크
- 상하좌우로 조건에 맞을 경우, DFS 탐색 계속 진행
- 해당 좌표에
P
가 있다면result
를 증가시킨다.
- 해당 좌표에
반응형
'백준' 카테고리의 다른 글
[백준] 4949: 균형잡힌 세상 (0) | 2025.04.18 |
---|---|
[백준] 2275: 부녀회장이 될테야 (0) | 2025.04.16 |
[백준] 7662: 이중 우선순위 큐 (0) | 2025.03.25 |
[백준] 7662: 이중 우선순위 큐 (0) | 2025.03.22 |
[백준] 1697: 숨바꼭질 (1) | 2025.03.22 |