문제 : boj26598
![](http://t1.daumcdn.net/tistory_admin/static/images/xBoxReplace_250.png)
필요 알고리즘
- 애드 혹(ad hoc), 그래프 탐색(dfs, bfs)
- 이 문제만의 규칙을 찾아 해결하는 애드혹 문제이다. 구현을 위해 그래프 탐색을 사용했다.
※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.
풀이
내 경우 이하의 로직으로 진행했다.
1. 맵의 좌측상단부터 우측 하단으로 진행하면서, 이미 찾은 직사각형임을 찾은 곳은 체크를 해둔다 (다시 직사각형의 여부를 확인하지 않아도 되도록).
![](http://t1.daumcdn.net/tistory_admin/static/images/xBoxReplace_250.png)
2. 아직 방문하지 않은 곳을 만났다면, 해당 지점부터 동일한 문자를 만날 때 까지 우측으로 진행하며 해당 직사각형의 너비를 계산한다. 그리고 동일한 문자를 만날 때 까지 아래로 진행하며 해당 직사각형의 높이를 계산한다. 예를들어 처음 A를 만났다면, 우측으로 가보니 A는 2칸이고 아래로 가보니 A는 3칸이었다. 따라서 해당 지점부터 2x3 지점을 모두 살펴보는 것이다. (코드의 findRange())
![](http://t1.daumcdn.net/tistory_admin/static/images/xBoxReplace_250.png)
3. 이 때 탐색 시 만약 해당 사이즈에서 다른 문자를 만나거나, 상하좌우로 한칸 씩 더 살펴보아 만약 동일한 문자가 있다면 직사각형이 아닌 경우이다. (코드의 possible())
![](http://t1.daumcdn.net/tistory_admin/static/images/xBoxReplace_250.png)
4. 위의 과정을 반복한다.
코드 : github
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
public static void main(String[] args) throws Exception {
new Main().solution();
}
int r, c;
char[][] arr;
boolean[][] v;
public void solution() throws Exception {
StringTokenizer st = new StringTokenizer(br.readLine());
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
arr = new char[r][c];
for (int i = 0; i < r; i++) {
String row = br.readLine();
for (int j = 0; j < c; j++) {
arr[i][j] = row.charAt(j);
}
}
v = new boolean[r][c];
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (v[i][j]) continue;
int[] range = findRange(i, j);
if (!possible(i, j, range[0], range[1])) {
System.out.println("BaboBabo");
return;
}
}
}
System.out.println("dd");
}
private boolean possible(final int rs, final int cs, final int re, final int ce) {
char target = arr[rs][cs];
for (int i = rs; i <= re; i++) {
for (int j = cs; j <= ce; j++) {
v[i][j] = true;
if (arr[i][j] != target)
return false;
if (i == rs && i-1 >= 0 && arr[i-1][j] == target)
return false;
if (i == re && i+1 < r && arr[i+1][j] == target)
return false;
if (j == cs && j-1 >= 0 && arr[i][j-1] == target)
return false;
if (j == ce && j+1 < c && arr[i][j+1] == target)
return false;
}
}
return true;
}
private int[] findRange(final int y, final int x) {
char target = arr[y][x];
int i = y;
while (i < r && arr[i][x] == target) i++;
int j = x;
while (j < c && arr[y][j] == target) j++;
return new int[]{i-1, j-1};
}
}
'PS > BOJ' 카테고리의 다른 글
[자바] 백준 2036 - 수열의 점수 (java) (0) | 2023.11.30 |
---|---|
[자바] 백준 25381 - ABBC (java) (0) | 2023.11.29 |
[자바] 백준 30536 - 시루의 산책 (java) (0) | 2023.11.28 |
[자바] 백준 12886 - 돌 그룹 (java) (0) | 2023.11.27 |
[자바] 백준 14567 - 선수과목 (Prerequisite) (java) (0) | 2023.11.26 |
댓글