[Algorithm]BOJ 1260 DFS와 BFS

문제

구현

 public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());   //정점의개수
        m = Integer.parseInt(st.nextToken());   //간선의개수
        v = Integer.parseInt(st.nextToken());   //탐색을 시작할 정점의 번호

        for (int i = 1; i <= n; i++) {
            list[i] = new LinkedList<>();      // 리스트 초기화
        }

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            list[s].add(e);
            list[e].add(s);
        }

🔻위 코드의 과정을 그림으로 나타내면 아래와 같다

• BFS

1. 시작점을 큐에 넣는다.
2. 시작점을 방문체크한다.
3. 큐가 비었다면 끝내기
4. 큐가 비지 않았다면 큐에 최상단에 있는 노드를 꺼낸다.
5. 해당 노드와 인접한 노드를 탐색하여, 방문하지 않은 노드라면 방문체크를 하고,
   큐에 넣어준다.
6. 3,4를 반복

public static Queue<Integer> q = new LinkedList<>();
public static boolean[] visit = new boolean[1001];

q.add(v);
visit[v] = true;

while (!q.isEmpty()) {
   int nowNode = q.poll();
   System.out.print(nowNode + " ");
   for (int i = 0; i < list[nowNode].size(); i++) {
       int nextNode = list[nowNode].get(i);
       if (visit[nextNode]) {
          continue;
       }
       q.add(nextNode);
       visit[nextNode] = true;
		}
    }
}

• DFS

1. 방문했으면 방문하지 않음
2. 갈 수 있는 곳 까지 쭉 따라감

 public static void dfs(int now) {
        System.out.print(now + " ");
        visit[now] = true;
        int size = list[now].size();
        for (int i = 0; i < size; i++) {
            int next = list[now].get(i);
            if (visit[next]) continue;
            dfs(next); // 다음 정점으로 이동
        }
    }