[백준] 유기농 배추(BufferedReader, DFS, 좌표 ➡️ 2차원 배열, 1012번, Java)

 

문제설명

입력 & 출력

나의 풀이

---

먼저 이번 문제는 배추밭의 가로, 세로가 주어졌을 때 배추가 있는 부분은 1 없는 부분은 0이며, 상하좌우로 이동하며 인접한 배추가 있으면 인접 배추로 이동할 수 있는 지렁이가 몇 마리 필요한 지 알아내는 문제입니다.

 

먼저 계속해서 호출되는 변수들을 가독성이 좋도록 전역변수로 선언합니다.

 

선언하는 전역변수에는 방문 여부를 저장할 visited배열, 배추밭의 지도 map, 입력으로 받을 변수들과 지렁이가 이동할 수 있는 배열을 초기화해 줍니다.

 

"상하좌우"로 이동할 수 있다고 정의할 것이기 때문에 x축 이동을 하는 dx는 좌, 우 y축을 이동을 하는 dy는 상, 하

 

DFS(깊이 우선 탐색)을 이용하여 배추 군집을 찾습니다. 현재 위치를 방문 처리하고, 상하좌우로 연결된 배추를 탐색하기 위해 4번의 반복문을 순회합니다.

 

현재 위치를 x, y인자로 받았기 때문에 현재 위치와 상하좌우로 이동할 수 있도록 dx와 dy를 접근하여 다음 위치를 nextX와 nextY로 저장을 합니다. 

 

그리고 범위를 넘어가지 않도록 조건문을 지정하고, 다음 위치가 방문하지 않았으며, 배추가 있는 경우(1) dfs를 재귀 호출 합니다.

 

 

main문에서는 BufferedReader클래스를 사용하여 입력을 빠르게 받아주고, StringTokenizer를 사용하여 입력을 공백을 기준으로 토큰으로 분리해 줍니다.

 

그리고 여기서 중요한 점❗️이 있습니다.

 

배추가 심어진 위치 K가 연속해서 들어오는 데 여기서 (x, y) 좌표는 배추가 심어진 위치를 나타냅니다.

 

일반적으로, 문제에서 주어진 좌표 (x, y)를 배열[y][x]로 매핑하는 것이 직관적입니다. 이유는 다음과 같습니다.

1. 문제에서 주어진 좌표(x, y)는 일반적으로 x축이 가로, y축이 세로를 의미합니다.
2. 배열의 인덱싱 [y][x]를 사용하면, 주어진 좌표를 그대로 배열로 옮길 수 있습니다.

따라서 [y][x] 형태인 [세로][가로] 형태로 배열을 초기화해줍니다.

 

그리고 입력받은 크기만큼 배열을 초기화해 주고, 지렁이의 개수를 초기화해줍니다.

 

그리고 각 배추가 심어진 위치를 x와 y로 입력을 받아 똑같이 배열[y][x] 형태로 배추를 심어줍니다.

 

 

그리고 62번째 줄에서 모든 지도를 순회하면서 배추가 있으며, 방문하지 않은 배추밭을 찾습니다.

 

그런 경우 dfs함수를 재귀 호출하여 인접한 배추밭을 모두 방문하고 나옵니다. 이를 통해 지렁이의 개수를 알 수 있습니다.

 

 

참고❗️

 

[JAVA] 좌표와 2차원 배열 매핑의 이해 (좌표 ➡️ 배열)

[JAVA] 입출력, BufferedReader, StringTokenizer, StringBuilder 알아보기