Notice
Recent Posts
Recent Comments
Link
변수의 기록
(코딩테스트) 백준_4963_섬의 개수 회고 본문
문제
내가 최초 제출 답안 (틀림)
public class testMain {
static int[][] map ;
static boolean[][] visted ;
static int w ;
static int h ;
static int[] x = {-1,1,0,0} ; //높이
static int[] y = {0,0,-1,1} ; //너비
static int count =0 ;
public static void main(String[] args) {
// TODO Auto-generated method stub
//bfs 큐에 담아서 예약 걸어둠 , visied 영역 표시 잘해야함 함수 초기 코드 + 상하좌우 검증 코드에도 조건 부합시 que로 while 루프 돌림
//dfs 재귀로 끝까지 보냄.
// 둘다 상하좌우 변수 선언 + map + visted + count 필요
Scanner sc = new Scanner(System.in);
w = sc.nextInt();
h = sc.nextInt();
map = new int[h][w];
visted = new boolean[h][w];
//지도 채우기
for(int i=0; i<h; i++) {
for(int j=0;j<w; j++) {
map[i][j]=sc.nextInt();
}
}
for(int i=0; i<h; i++) {
for(int j=0;j<w; j++) {
if(!visted[h][w]) bfs(0,0); // 방문한적 없어? 그럼 bfs 시작
}
}
System.out.println(count); // 마지막에 카운트 출력
}
public static void bfs(int h , int w ) {
Queue<int[]> q = new LinkedList<>();
visted[h][w] = true;
int [] first = {h,w};
q.offer(first);
while(!q.isEmpty()) { //q 체킹
int[] que= q.poll();
int nh = que[0] , nw = que[1];
if(map[nh][nw]==1) count++; // 현재 위치 섬이야?
int nextH ; //다음 탐색할 높이?
int nextW ; //다음 탐색할 너비?
for(int i =0 ; i<4;i++) { // 상하좌우 탐색 고고
nextH = nh + x[i];
nextW = nw + y[i];
if(nextH > 0 && nextW > 0 && nextH < h && nextW < w) { //범위내인지 체크
if(!visted[h][w] ) { // 방문한적 없고 , 섬인지 체크
visted[h][w] = true;
int[] next = {nextH,nextW};
q.offer(next);
if(map[nextH][nextW]==1) {
count ++;
}
}
}
}
};
}
}
우선 문제 요약 (4963번)
- 1은 땅, 0은 바다.
- 상하좌우 + 대각선까지 포함하여 연결된 1들은 하나의 "섬"으로 간주.
- 여러 테스트 케이스가 주어지며, 각 테스트 케이스마다 섬의 개수를 출력해야 함.
- 입력 종료 조건: w h = 0 0
나의 코드 흐름 요약
- map, visited, bfs()를 활용해 섬을 셈.
- x, y 배열로 상하좌우 4방향을 탐색.
- BFS를 돌면서 섬이면 count++ 증가.
❌ 문제점 및 오류
1. 입력을 한 번만 받고, 여러 테스트 케이스를 고려하지 않음
- 문제는 여러 테스트 케이스가 주어짐.
- 현재는 w, h를 한 번만 받고 종료됨.
🔧 해결법: while (true) 루프 안에서 w == 0 && h == 0이면 종료하도록 해야 함.
2. 탐색 방향이 4방향밖에 없음
- 문제는 **8방향(상하좌우 + 대각선)**을 봐야 함.
🔧 dx, dy를 8방향으로 바꿔야 함:
int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
3. if (!visited[h][w]) bfs(0,0) 라인이 잘못됨
- 무조건 (0,0)부터 BFS 시작하고 있음.
- 그리고 조건도 visited[h][w]인데, h와 w는 맵 크기라서 인덱스 범위 초과 오류가 발생함.
🔧 수정:
if (!visited[i][j] && map[i][j] == 1) {
bfs(i, j);
count++;
}
4. BFS 내에서 섬을 만날 때마다 count++함
- 섬 개수는 BFS 하나당 1개만 세야지, BFS 내부에서 count++하면 섬 내부에서 여러 번 셈.
🔧 해결: count++는 BFS 외부에서 한 번만 해야 함. 내부에서 하면 X
5. 방문 체크가 잘못된 좌표로 되어 있음
if (!visited[h][w]) ...
- 여기도 nextH, nextW 써야 함. h, w는 처음 시작 좌표
🔧 수정:
if (!visited[nextH][nextW] && map[nextH][nextW] == 1) {
visited[nextH][nextW] = true;
q.offer(new int[]{nextH, nextW});
}
개선된 코드
import java.util.*;
public class Main {
static int[][] map;
static boolean[][] visited;
static int w, h;
// 8방향: 상하좌우 + 대각선
static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
w = sc.nextInt();
h = sc.nextInt();
if (w == 0 && h == 0) break;
map = new int[h][w];
visited = new boolean[h][w];
// 지도 입력
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
map[i][j] = sc.nextInt();
}
}
int count = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (!visited[i][j] && map[i][j] == 1) {
bfs(i, j);
count++;
}
}
}
System.out.println(count);
}
sc.close();
}
public static void bfs(int startX, int startY) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{startX, startY});
visited[startX][startY] = true;
while (!q.isEmpty()) {
int[] current = q.poll();
int x = current[0];
int y = current[1];
for (int i = 0; i < 8; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < h && ny < w) {
if (!visited[nx][ny] && map[nx][ny] == 1) {
visited[nx][ny] = true;
q.offer(new int[]{nx, ny});
}
}
}
}
}
}
최종 회고.
1. 상하좌우 뿐만 아니라 , 대각선까지 고려하지 못함. (문제 파악X ) + 연결된 섬을 하나인걸 인지 못했음.
2. Scanner 대신 -> BufferedReader 습관화
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
'기타 > 코딩테스트' 카테고리의 다른 글
(코테) 백준_4179_불! bfs (0) | 2025.05.10 |
---|---|
(코딩테스트) 백준_2559_수열 (윈도우 슬라이드) (0) | 2025.05.06 |
(코테) 기능개발_프로그래머스 (0) | 2025.05.02 |
(코테) 체육복_프로그래머스 (탐욕법) (1) | 2025.05.02 |
(코테) 최소직사각형_프로그래머스 (완전 탐색) (0) | 2025.05.01 |