오늘의 키워드
•
그래프 탐색
•
BFS / DFS
•
8방향 탐색
•
BufferedReader 문제
•
자바 & 파이썬 풀이 비교
문제 파악 및 풀이
"상하좌우 및 대각선을 포함한 8방향으로 연결된 1의 묶음을 '섬'으로 간주하고, 그 개수를 세어라."
문제를 보자마자 BFS를 활용해서 풀 수 있는 문제라는 생각이 들었다.
1년 전에 Python으로 풀었던 문제라 반가웠고, 이번에는 Java로 다시 도전해 볼 수 있어 의미 있었다.
Java 풀이
class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
class Main {
public static final int MAX_SIZE = 50;
public static int w, h;
public static int[][] matrix = new int[MAX_SIZE][MAX_SIZE];
public static boolean[][] isChecked = new boolean[MAX_SIZE][MAX_SIZE];
public static Deque<Pair> dq = new ArrayDeque<>();
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
while (init()) {
isCheckedInit();
int cnt = 0;
for (int i = 0; i < w; i++) {
for (int j = 0; j < h; j++) {
if (matrix[i][j] == 1 && !isChecked[i][j]) {
bfs(i, j);
cnt++;
}
}
}
System.out.println(cnt);
}
}
public static void bfs(int x, int y) {
dq.add(new Pair(x, y));
isChecked[x][y] = true;
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
int nx = x + i;
int ny = y + j;
if (canGo(nx, ny)) {
dq.addLast(new Pair(nx, ny));
isChecked[nx][ny] = true;
}
}
}
}
public static boolean canGo(int x, int y) {
return 0 <= x && x < w && 0 <= y && y < h && !isChecked[x][y] && matrix[x][y] == 1;
}
public static void isCheckedInit() {
for (int i = 0; i < w; i++) {
for (int j = 0; j < h; j++) {
isChecked[i][j] = false;
}
}
}
public static boolean init() throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
h = Integer.parseInt(st.nextToken());
w = Integer.parseInt(st.nextToken());
if (w == 0 && h == 0) return false;
for (int i = 0; i < w; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < h; j++) {
matrix[i][j] = Integer.parseInt(st.nextToken());
}
}
return true;
}
}
Java
복사
Python 풀이
Python은 DFS를 활용한 풀이로, 전체적인 코드가 훨씬 더 간결했다.
import sys
input = sys.stdin.readline
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
def dfs(x, y):
stack = [(x, y)]
while stack:
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < h and 0 <= ny < w and arr[nx][ny] == '1':
stack.append((x, y))
arr[nx][ny] = '0'
x, y = nx, ny
break
else:
x, y = stack.pop()
return 1
in_, put_ = map(int, input().rstrip().split())
while in_ != 0 and put_ != 0:
w, h = in_, put_
arr = [input().rstrip().split() for _ in range(h)]
ans = 0
for x in range(h):
for y in range(w):
if arr[x][y] == '1':
arr[x][y] = '0'
ans += dfs(x, y)
print(ans)
in_, put_ = map(int, input().rstrip().split())
Python
복사
BufferedReader 관련 문제 및 원인 분석
Java로 작성하면서 가장 헷갈렸던 부분 중 하나는 BufferedReader로 입력받을 때 발생한 예외적인 동작이었다.
처음엔 문법 오류도 없고, 로직도 분명 맞다고 생각했는데 계속해서 실패가 나왔다.
그러다 BufferedReader 선언 위치를 init() 안에서 밖으로 옮기자 갑자기 정답이 나오기 시작했다.
// ❌ 오답
public static boolean init() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // → 매번 생성
...
}
// ✅ 정답
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // → 한 번만 생성
Java
복사
원인
BufferedReader는 내부적으로 System.in을 버퍼링하고 사용하는데, System.in은 단 한 번만 순차적으로 읽히는 단방향 입력 스트림이다.
BufferedReader를 매번 새로 생성하면, 같은 System.in을 참조하더라도 이미 커서가 지나간 곳을 읽으려 하기 때문에 null을 반환하거나 입력이 꼬이는 문제가 발생한다.
그럼 System.in은 동기적인가?
•
System.in 자체는 동기적 입력 스트림이다.
→ 즉, 입력이 들어올 때까지 read() 호출이 블로킹되어 기다린다.
◦
하지만 문제는 BufferedReader를 재생성하며 System.in을 중복해서 참조한 것.
◦
커서가 이미 지나간 곳이거나, 중간 줄을 잘못 읽어오는 문제가 발생한 것이다.
오늘의 회고
어려웠던 점
•
Java에서 BufferedReader의 입력 처리 방식 때문에 에러가 났다.
•
동기적 입력 특성과 버퍼 처리 방식에 익숙하지 않아서 디버깅에 시간을 소모했다.
개선점
•
Java에서 입출력을 처리할 땐 BufferedReader, Scanner, StringTokenizer 각각의 특성과 차이점을 더 정확히 이해하고 활용해야겠다.
•
디버깅 시 로직만 옳으면 된다는 생각보다는, 입력-출력 흐름 전체를 면밀히 보는 습관이 중요하다는 걸 다시금 깨달았다.