inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

섬나라 아일랜드 DFS

79

이동건

작성한 질문수 10

0

이전강의에서 풀엇던것처럼 ch체크 배열만들고 시계방향 9,12,3,6시 방향으로만 체크해서 이렇게 만들었는데

강사님이 강의 때 하셧던거에 비하면 효율이 많이 떨어지는지 궁금해서 질문 남깁니다

 

 

package section9;

import java.util.ArrayList;
import java.util.Scanner;

public class Main13 {
	static int[] dx= {-1,0,1,0};
	static int [] dy= {0,1,0,-1};
	static int[][] ch,dir,map;
	static int n,answer;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner s=new Scanner(System.in);
		ArrayList<Integer> list = new ArrayList<>();
		answer=0;
		n=s.nextInt();
		map= new int[n][n];
		ch= new int[n][n];
		dir= new int[n][n];
		for(int i=0;i<n;++i) {
			for(int z=0;z<n;++z) {
				map[i][z]=s.nextInt();
			}
		}
		for(int i=0;i<7;++i) {
			for(int z=0;z<7;++z) {
				if(map[i][z]==1 && ch[i][z]==0) {
					DFS(i,z);
					if(answer>1) {
						list.add(answer);
						answer=0;
					}
				}else {
					answer=0;
					continue;
				}
			}
		}
		System.out.println(list.toString());
		System.out.println(list.size());
	}
	static void DFS(int x,int y) {
		if(map[x][y]==1) {
			answer++;
		}
		if(ch[x][y]==1) return;
		if(map[x][y]==0) return;
		if(x<0 || x>6 || y<0 || y>6) {
			return;
		}else {
			ch[x][y]=1;
			for(int i=0;i<4;++i) {	
				int nx= x+dx[i];
				int ny=y+dy[i];
				if(nx>=0 && nx<7 && ny>=0 && ny<7 && 
ch[nx][ny]==0 && map[nx][ny]==1) {
					DFS(nx,ny);
				}
			}
			
		}
	}

}

java 코딩-테스트

답변 2

0

김태원

안녕하세요^^

위 코드는 대각선으로 연결된 섬을 찾지 못하는 것 같습니다. 그리고 격자 하나가 단독으로 1이어도 섬으로 간주합니다. 아래 입력은 섬의 개수가 2개 입니다. 님의 코드는 0개가 나옵니다. 영상의 방법처럼 8방향을 직접 탐색하는 것을 추천합니다.

4

1 0 0 0

0 1 0 0

0 0 1 0

1 0 0 0

0

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.

이동건님께서 섬나라 아일랜드 문제에 대해 질문해주셨군요. 님의 질문 내용은 DFS(깊이 우선 탐색)을 활용하여 섬을 세고자 하는 코드의 효율성과 관련되어 있습니다. 코드 리뷰를 통해 개선 방향과 효율성을 논하는 것은 매우 훌륭한 습관입니다!

우선, 섬을 세는 문제는 DFS나 BFS를 통해 해결할 수 있는 전형적인 문제로, 주변의 네 방향(상하좌우) 또는 대각선을 포함해 여덟 방향을 탐색하면서 연결된 1을 찾아 탐색합니다.

이미 구현하신 코드에서 몇 가지 개선할 수 있는 점을 말씀드리자면:

  1. 방문 체크 배열(ch): 현재 ch 배열로 방문 체크를 하고 계신데, DFS 내부에서 중복 방문을 방지하기 위해 필수적입니다. 하지만, 함수 초입에서 if(ch[x][y]==1) return; 이 부분으로 방문 체크를 좀 더 일찍 할 수 있습니다.

  2. 경계 조건: if(x<0 || x>6 || y<0 || y>6) 로 경계 체크를 하고 계신데, 반복문 내에서는 인덱스가 맵의 크기를 초과하지 않도록 유의하셔야 합니다. 현재 배열 크기는 최대 7로 설정되어 있으니, n을 직접 활용하는 것도 좋습니다.

  3. 네 방향 탐색: 현재 네 방향만 탐색하고 있어서 대각선의 연결은 탐색 대상에 포함되지 않지만 의도하신 방향이 맞다면 괜찮습니다. 하지만 대각선도 연결되도록 탐색하길 원한다면 방향 배열에 대각선을 포함시키는 것이 좋습니다.

  4. 효율성: 효율성을 높이기 위해서는 정점을 방문할 때마다 필요한 추가 작업을 최대한 줄이는 방향이 있습니다. 님께서 사용하신 방식보다 개선할 수 있는 여지가 크지는 않습니다만 로직 자체는 이미 재귀를 통해 잘 동작하고 있습니다.

위의 포인트는 알고리즘 설계에 있어서 코드의 개선 여부와 효율성 증대를 위해 고려할 수 있는 사항들입니다. 섬의 개수를 세고자 하는 질문에서 많이 따라오는 질문 중 하나입니다.

추가로, 기존 답변 을 참고하실 수 있도록 링크를 첨부드리니 비교해보시면 좋을 것 같습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

안녕하세요. 바뀐 채점사이트 관련해서 문의드립니다.

0

33

1

갑자기 채점 사이트가 바뀌었어요

0

34

1

문제 리스트 페이지

0

29

1

채점 사이트 관련 질문드립니다

0

24

1

봉우리 문제 질문입니다

0

84

2

씨름 선수 문제에서 각 선수의 몸무게나 키가 같을 수도 있다면?

0

65

0

이 코드랑 영상 코드중에 뭐가 더 좋은 코드인가요?

0

72

0

가중치 방향 그래프에서 가중치가 0인 간선을 표현하는 방법

0

67

1

좌표 정렬 문제 이 코드가 왜 틀린지 모르겠습니다 ㅠㅠ

0

85

2

6-7 강의에서

0

48

1

6-6. 장난꾸러기 질문 있습니다.

0

46

1

강의 수강후 코딩테스트

0

111

1

answer 변수 사용 여부

0

46

1

2중 for문

1

85

2

2-11. 임시반장정하기 (Runtime Error)

0

63

1

혹시 LinkedList 같은 자료 구조들은 따로 배우지 않나요?

0

70

1

이런 풀이는 어떨까요

0

44

1

자바 스트림 방식의 효율성 질문 드립니다.

0

57

1

알고리즘 자료 구조들..

0

63

1

StringBuilder vs BufferdWriter

0

48

1

원더랜드(프림)

0

50

1

이런 코드는 어떤가요?

0

61

1

bfs 풀이

0

57

1

병합정렬

0

57

1