전체 글

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

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

문제설명입력 & 출력나의 풀이먼저 이번 문제는 배추밭의 가로, 세로가 주어졌을 때 배추가 있는 부분은 1 없는 부분은 0이며, 상하좌우로 이동하며 인접한 배추가 있으면 인접 배추로 이동할 수 있는 지렁이가 몇 마리 필요한 지 알아내는 문제입니다. 먼저 계속해서 호출되는 변수들을 가독성이 좋도록 전역변수로 선언합니다. 선언하는 전역변수에는 방문 여부를 저장할 visited배열, 배추밭의 지도 map, 입력으로 받을 변수들과 지렁이가 이동할 수 있는 배열을 초기화해 줍니다. "상하좌우"로 이동할 수 있다고 정의할 것이기 때문에 x축 이동을 하는 dx는 좌, 우 y축을 이동을 하는 dy는 상, 하 DFS(깊이 우선 탐색)을 이용하여 배추 군집을 찾습니다. 현재 위치를 방문 처리하고, 상하좌우로 연결된 배추를 ..

프로그래밍을 하다 보면 좌표와 배열을 매핑하는 작업이 필요할 때가 많습니다. 특히 2차원 배열을 다루는 알고리즘 문제에서는 좌표 (x, y)를 배열에 올바르게 맵핑하는 것이 중요합니다. 필자 또한 헷갈리는 부분이 있어 이번 글에서는 좌표와 배열의 매핑 방법을 자세히 알아보겠습니다. 좌표와 배열의 기본 개념❓먼저 좌표와 배열의 기본 개념에 대해서 정리해 봅시다. 좌표 (x,y)좌표는 공간에서 위치를 나타내기 위해 사용하는 숫자 쌍 또는 그 이상의 수의 집합입니다.좌표는 일반적으로 x는 열(column), y는 행(row)를 의미합니다.예를 들어 좌표 (3,4)는 x축에서 3만큼 오른쪽으로, y축에서 4만큼 위쪽으로 이동한 위치를 나타냅니다.2차원 배열[행][열]배열은 동일한 타입의 변수들을 하나의 묶음으로..