dfs

문제설명입력 & 출력 나의 풀이 이번 문제는 DFS와 BFS를 활용하여 주어진 정점 V로부터 탐색하는 정점을 출력하는 문제입니다. DFS와 BFS에 대한 개념이 있으시다면 어렵지 않게 풀 수 있는 문제였습니다.  먼저 가독성을 위해서 전역변수로 사용할 수 있는 변수들은 전역변수로 선언해 줍니다.  main문 먼저 설명하자면, 빠른 입력을 위해서 BufferedReader클래스를 사용하여 입력을 받아주고, StringTokenizer를 사용하여 간선이 연결하는 두 정점의 번호를 공백을 기준으로 분리를 해줍니다. 그리고 입력받은 정점의 크기만큼 정점을 나타내는 graph배열을 초기화해 줍니다. 이때 문제에서 나왔듯이 정점은 1부터 시작하기 때문에 "+1"을 해줘야 합니다. 그리고 간선의 개수 M만큼 반복하는..

문제설명입력 & 출력 나의 풀이 컴퓨터의 개수 N과 각 컴퓨터 간의 연결 상태를 나타내는 2차원 배열 computers가 주어질 때 서로 연결된 컴퓨터들을 하나의 네트워크로 간주하고 전체 네트워크의 개수를 리턴하는 문제입니다. 해당 문제는 DFS로 연결된 노드들을 쉽게 찾을 수 있습니다. 먼저 Solution에서는 입력으로 주어지는 컴퓨터의 개수 n과 연결에 대한 정보 배열인 computers를 인자로 받습니다. 입력받은 컴퓨터의 개수만큼 노드가 있어야 하기 때문에 n만큼의 크기를 가지는 visited배열을 초기화를 해줍니다. 연결된 네트워크의 개수를 0으로 초기화해주고, 모든 노드들을 순회하는 반복문을 선언합니다. 만약 해당 노드가 아직 방문하지 않은 노드라면, dfs를 수행하여 해당 네트워크의 모든 ..

문제설명입력 & 출력나의 풀이이번 문제는 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 문제입니다.  먼저 계속해서 호출되는 변수들은 가독성이 좋도록 전역변수로 선언해 줍니다. 그리고 방문 여부를 체크할 visited배열과, 그래프를 저장할 graph배열을 선언해줍니다.  DFS함수에서는 먼저 인자로 받은 현재위치를 방문 처리해 주고, 현재 노드 node에서 연결된 다음 노드(next) 들을 찾아서, 아직 방문하지 않은 노드들에 대해 DFS함수를 재귀적으로 호출합니다.  main문에서는 빠른 입력을 위해서 BufferedReader클래스를 사용하여 입력을 받아주고, StringTokenizer를 사용하여 입력받은 간선의 양 끝점 u와 v를 공백을 기준..

문제설명입력 & 출력나의 풀이먼저 이번 문제는 1 : 땅, 0 : 바다로 이루어진 지도가 주어졌을 때 섬의 개수를 구하는 문제입니다. 단 섬이 연결되어 있는 경우는 하나의 섬으로 간주하기 때문에 이 점을 고려해야합니다. 이동할 수 있는 방향은 가로,세로,대각선입니다.  먼저 계속해서 호출되는 변수들을 가독성이 좋도록 전역변수로 선언합니다. 그리고 섬이 이동할 수 있으면 하나의 섬으로 간주하기 때문에 섬에서 다른 섬으로 이동할 수 있는 방향을 지정해줍니다.(좌상단,우상단,좌하단,우하단,상,하,좌,우) 문제에서 가로,세로,대각선을 이동할 수 있다고 했기 때문에 위와 같이 이동 방향을 지정해줍니다. 이동방향에 대한 자세한 설명은 참고에 있는 포스트를 참고해주세요. 그리고 DFS함수를 선언해줍니다. DFS함수에..