[백준 JAVA] 1260번: DFS와 BFS - 스승님과 같이 풀어보기

https://www.acmicpc.net/problem/1260

 

 

코드 짜기 전에 해야할 것

1. 문제 읽기 (깊이)

2. 써야 되는 변수 정리

    2-1. 전역변수, 즉 메인 클라스 내에서 써야하는 변수 인지 class안에서 써야하는 변수인지 체크

    2-2. 메인에서 써야하는 변수는 테스트케이스 별로 초기화가 필요한 변수, static변수는 다른 method에서 사용해야 되는             변수를 선언한다.

3. 코드 짜는 순서 정리

   3-1. 입력

          > n, m, v 입력
          > a : 맵 정보 생력 및 입력
          > visited 생성

 

   3-2. dfs 호출
            v isited 초기화
            개행
   3-3. bfs 호출

- 방문 처리 언제?

함수에 들어갈때 해주기, 함수에서 나올때 해주기,  미리 들어갈때 해주기, 각각 케이스별로 다르지만 미리들어갈때 해주는것이 좋다.

dfs 구현

bfs 구현
 

어떻게 구현했냐

1. 변수정리

	public static int N, M, V;
	public static List<Integer>[] graph;
	public static int[] visited;
	static StringBuilder sb = new StringBuilder();

 

리스트는 사실 배열로 선언해서 사용하는것이 불가능하다. (generic의 의미가 떨어지기 때문에, 뭐든 다들어가 버림)

하지만 코테에서는 어차피 다른것이 들어갈 이유가 없으므로 편의상 사용한다.

! 인접 리스트 생성하는것 외워두기

! visited는 int형으로 생성하는게 실행시간 단축에 도움이 됨.. 큰 차이는 없지만 boolean의 경우 1byte를 다시 32bit로 변환해서 사용하기 때문에 연산을 한번 더한다.

 

2. 입력값 받아오기, 리스트 정렬

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		V = Integer.parseInt(st.nextToken());
		graph = new ArrayList[N + 1];
		visited = new int[N + 1];
		for (int i = 1; i < N + 1; i++) {
			graph[i] = new ArrayList<>();
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int i1 =Integer.parseInt(st.nextToken());
			int i2 =Integer.parseInt(st.nextToken());
			graph[i1].add(i2);
			graph[i2].add(i1);
		}
		for(int i=1; i<N+1; i++) {
			Collections.sort(graph[i]);
		}

 

BufferedReader를 쓸꺼다. System.in을 받아오겠지? 이것은 InputStreamReader로 묶어주고 (입력이라 InputStream, Reader는 문자열을 받아오기 때문에) 빠르게 버퍼단위로 받아오기 위해서 다시 BufferedReader로 묶어준다. 새로운 객체를 생성하는 개념이므로 둘다 new를 해줌.

 

한줄씩 받아온 BufferedReader를 " " 단위로 끊어서 넣어주기 위해 StringTokenizer를 선언해준다. 아직 객체를 만들어주지 않은 이유는 밑에서 따로 따로 만들어 줄꺼이기 때문 -> 우선 한줄 받아와서 N, M, V 받아오고 다음에 주어진 간선에 대한 정보는 for문을 돌때마다 받아와주려고

 

StringTokenizer는 Token()단위로 문자열을 받아온다. 따라서 st.nextToken()을 이용해서 넣어줄껀데 문자열이기 때문에 인트형으로 바꿔주는 작업이 필요하다. Integer.parseInt

 

N, M, V를 받아왔다면 이를 이용해서 만들어야하는 리스트랑 visited를 만든다. 

값의 범위를 N+1로 한 이유는 0번부터하는것이 아닌 1번노드와 이어지는 간선은 graph[1]에 저장하고, 방문체크도 visited[1]에 저장할것이기 때문에 하나 더 필요하다.

 

다음으로 graph[0]부터 graph[N+1]까지 ArrayList<>()를 넣어준다. 아까 말했듯이 원래는 이렇게 쓰면 안되는데 코테에서는 이렇게 사용한다.아까는 graph의 리스트배열을 담을 배열을 선언 각각의 배열마다 ArrayList 선언

 

간선에 대한 정보를 받아오기 위해 for문 0부터 m까지 반복 (m개의 간선이므로) st 다시 선언해서 for문 돌때마다 한줄씩 받아오기, 총 두개를 int형으로 받아온 다음에 각각 graph의 인자로 넣어준다. 양방향이기 때문에 순서를 바꿔서 한번더 넣어준다. (graph[i]에 인자가 있다면 i와 해당인자가 연결된것으로 간주하는 인접리스트 생성)

 

작은 수부터 방문하기로 했으니까 graph배열마다 정렬해줌.

 

3. dfs와 bfs 호출 후 최종 출력

		// 2. dfs 호출
		visited[V] = 1;
		dfs(V);
//		visited[V] = 0;


		// 4. bfs 호출
		sb.append("\n");
		bfs(V);
		System.out.println(sb);

 

 

처음 값의 visited를 1로 초기화 (방문처리)

dfs 호출

visited[v] = 0으로 초기화 해주지 않은 이유는 위에서 다돌았다면 visited가 전부 1로 되어있다.

이를 이용해서 다음 bfs에서는 visited가 1이라면 방문하지 않았다고 본다. 1로 초기화해준셈

 

개행후 bfs 호출, 전체 출력

 

4. dfs 구현

	public static void dfs(int start) {
		sb.append(start + " ");
		for(int i = 0; i<graph[start].size(); i++) {
			int next = graph[start].get(i);
			if(visited[next] == 0) {
				visited[next] = 1;
				dfs(next);
//				visited[next] = 0;
			}
		}
	}

우선 start로 받아온 값을 출력

 

그 뒤 다음에 들어가야할 곳으로 재귀 해주는데 graph[start] 전에 들어갔던데에 있는 인자를 next로 호출

 

만약 방문하지 않은 노드라면(visited[next] == 0)

1. 그 노드 방문처리

2. start에 해당 노드로 재귀

3. 완전탐색이 한번이 아니라 다음에도 들어가야한다면 방문 초기화 필요하지만 이번에는 끝까지 찍고 다시 돌지 않을거기 때문에 방문 초기화 X

 

5. bfs 구현

	public static void bfs(int start) {
		Queue<Integer> q = new LinkedList<>();
		visited[start] = 0;
		q.offer(start);
		while(!q.isEmpty()) {
			// 1. Q에서 방문 지점 꺼냄
			int cur = q.poll();
			// 2. 출력
			sb.append(cur+" ");
			
			// 3. 방문 지점으로부터 가능한 다음 지점 탐색
			for(int i = 0; i<graph[cur].size(); i++) {
				int next = graph[cur].get(i);
				if(visited[next] == 1) {
					visited[next] = 0;
					q.offer(next);
				}
			}
		}
	}

 

1.Q 생성 LinkedList 객체를 Q로 생성

 

2. 들어온 노드 우선 방문처리 아까 dfs와 마찬가지로 밬에서 해줘도 된다.

 

3. 들어온값 큐에 먼저 넣어주기(초기값만)

 

4. while문을 통해 q가 비워지기 전까지 반복

  4-1. 꺼내서 cur에 저장

  4-2. 출력

  4-3. for문으로 해당 노드의 그래프(리스트)가 가지고 있는 인자를 전부 큐에 넣어주기

5. for문

 0번째부터 방금 출력한 노드가 가지고 있는 인자를 순회해서 큐에 넣어줄꺼기 때문에 graph[cur].size() 만큼 반복

  5-1. 다음 넣어줄 노드 next에 저장

  5-2. 만약 방문하지 않았다면 아까와 달리 0일때가 아니라 1일때

  5-3. 해당 노드 방문 처리

  5-4. q에 넣어주기 

 

q에 넣어야 될 것들을 다 넣어줬다면 4번으로 돌아가서 while문 반복

 

다돌았다면 큐가 다 비워지고 모든 노드의 visited가 0으로 초기화

 

q에 넣어줄때는 offer와 poll사용 권장

 

 

배운점

1. dfs, bfs는 어렵다.

2. 하지만 연습하면 할 수 있다.

3. 무작정 문제를 보고 코드를 짜는게 아니라 뭐가 들어가고 어떤게 필요한지 메모장에 적고 시작 순회, 재귀를 하더라도 어떤식으로 동작할것인지 그림판에 그려보고 시작.

4. scanner뿐만 아니라 sb, st, br 적극적으로 사용 -> 어떤 상황에 어떤 입력이 와도 효율적으로 처리가능

5. 방문처리를 언제 할것인지 언제 재귀할것인지 많은 사례를 보고 익히자

6. 배열의 범위를 처음에 잘 생성해 놓으면 나중에 그 부분에 의심이 덜 생긴다.

7. 스승님은 sysout을 사용하면서 재귀가 어디까지 돌았고 어떤게 안들어가고 들어가는지 체크하신다. 디버그를 이용하는 방법도 있겠지만 우선은 이런 방식으로 디버그

8. 진짜 화이팅