inflearn logo
강의

Khóa học

Chia sẻ kiến thức

[Java/Java] Thuật toán DFS mà ngay cả sinh viên giáo dục khai phóng cũng có thể hiểu được! - Giới thiệu

Số lượng đảo (Baekjun 4963)

code의 어디가 잘못된지 도저히 모르겠습니다..

Đã giải quyết

269

beomth

12 câu hỏi đã được viết

1

안녕하세요. 해당 문제의 코드를 다음과 같이 짰는데, 출력하면 항상 0이 출력됩니다.
강의에 나온 부분과 거의 동일한데, 어느 부분에서 오류가 발생하는지 잘 모르겠습니다. 감사합니다.

import java.util.*;
import java.io.*;

class Main {

	final static int MAX = 50 + 10;
	static boolean[][] map;
	static boolean[][] visited;
	static int W, H;
	static int[] DirY = {-1, -1, -1, 0, 0, 1, 1, 1};
	static int[] DirX = {-1, 0, 1, -1, 1, -1, 0, 1};
	
	public static void dfs(int y, int x) {
		visited[y][x] = true;
		
		for(int i = 0; i < 8; i++) {
			int newY = y + DirY[i];
			int newX = x + DirX[i];
			if(map[newY][newX] && visited[newY][newX] == false) {
				dfs(newY, newX);
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
			
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
		// 0. 입출력 
		while(true) {
		
			StringTokenizer st;
			st = new StringTokenizer(br.readLine());
			
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());
			
			// 마지막 입력 값이 0이면 while 문 빠져나오기
			if(W == 0 && H == 0)
				break;

			map = new boolean[MAX][MAX];
			visited = new boolean[MAX][MAX];
			for(int i = 1; i <= H; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j = 1; j <= W; j++) {
					map[i][j] = (Integer.parseInt(st.nextToken()) == '1') ? true : false;
				}
			}
			
			int answer = 0;
			for(int i = 1; i <=H; i++) {
				for(int j = 1; j <=W; j++) {
					if(map[i][j] && visited[i][j] == false) {
						dfs(i, j);
						answer++;
					}
				}
			}
			
			bw.write(String.valueOf(answer));
			bw.newLine();
		}
		
		bw.close();
		br.close();
	}
}

java 코딩-테스트 알고리즘 dfs

Câu trả lời 1

1

gaebaljob

안녕하세요 버럼님 :)

코드 확인했는데 거의 정답에 가까운 것 같아요. 유일하게 수정해야되는 부분은 map[i][j]에 값을 담을 때 입니다! 이때 st.nextToken() == '1'과 비교하고 있기 때문에 1이라는 문자와 비교하고 있습니다. 다만 nextToken으로 입력 받은 형태는 정수형이기 때문에 어떤 정수도 ASCII 문자 1과 같다고 판단하지 않아서 map의 정보가 정상적으로 담기지 않는 것으로 보여요.

그래서 이 부분만 '1'과 비교하지 않고 1과 비교하도록 수정하면 될 것 같습니다!

 

이런 류의 버그를 디버깅할 때는 가장 먼저 입력이 제대로 들어왔는지를 확인해야 하는데, 지금 케이스는 바로 잡을 수 있을 것 같아요! 시험장에서는 버그도 직접 잡을 수 있어야 하니 잘 기억해두셔도 좋을 것 같습니다!

공부 화이팅하세요!

dfs 부문을 이렇게 작성해도 되나요?

1

71

1

x랑 y를 거꾸로 쓰는 개념이 너무 헷갈립니다...

1

94

2

dfs 파라미터에 count를 넣는이유

1

62

2

graph 채울때 for문 설계 질문

1

71

2

질문있습니다.

1

71

1

다른 강의 언제나오나용?

1

92

2

노드간 거리 계산

1

145

1

안녕하세요, 혹시 다른문제도 여쭤볼 수 있을까요?

1

130

1

최근에 올린 질문, 코드블럭으로 공유드립니다!

1

143

1

질문이 있습니다. dfs 메서드에 order를 이렇게 구현하면 안되는 이유가 무엇인가요?

0

133

2

깊이우선탐색2 백준 24480 수업노트에...

1

115

1

백준 24479 문제 제출 결과 "틀렸습니다" 라고만 나와서 어떤 부분이 틀렸는지 잘 모르겠어요 피드백 부탁드립니다

1

249

3

graph 만들때 boolean[][] 으로 만드는 경우랑 int[][] 나 ArrayList<Integer>[] 로 만드는 기준이 어떻게 되나요?

1

201

2

graph를 2차원 배열 또는 List로 하는 기준을 어떤식으로 잡으면 좋을까요...?

1

224

1

강사님 안녕하세요! 깊이 우선 탐색 2 (백준 24480)에서 제공하는 풀이 코드에서 궁금한 점이 있어서 질문 드립니다!

1

325

3

촌수 계산

1

354

3

연결 요소의 개수 (백준 11724)

1

267

1

백준 24479 문제 시간 초과 질문 드려요

1

382

1

백준 실행시 틀립니다.

1

372

1

재귀대신 스택으로 구현하면 안될까요?

1

408

1

dfs 매개변수에서 y,x 를 왜 순서를 반대로 쓰셨는지 궁금합니다.

1

370

1

안녕하세요 11724번 질문드려요!

2

313

1

출력할 때 BufferedWriter? StringBuilder?

1

508

1

answer++ 위치 질문

1

254

1