[백준] 바닥 장식 (BufferedReader, dfs, 1388번, Java)

qjs

 

문제설명

입력 & 출력

나의 풀이

 

이번 문제의 주요 목표는 '-'와 '|'로 이루어진 바닥 장식의 개수를 세는 것입니다. 이를 위해 DFS를 사용하여 각 장식의 연결된 부분을 방문하고, 이미 방문한 부분은 다시 방문하지 않도록 합니다.

 

먼저 코드의 가독성을 위해서 아래의 변수 및 배열을 전역 변수로 선언해 줍니다.

• 방바닥의 크기인 N과 M
• 방문 여부를 저장할  visitied 배열
• 바닥 장식을 저장할 floor 배열

 

빠른 입력을 위해서 BufferedReader클래스를 사용하여 입력을 받아주고, N과 M을 공백을 기준으로 분리하여 token에 저장합니다.

 

입력받은 바닥의 가로 N 세로 M의 크기만큼 순회를 하면서, charAt() 메서드를 사용하여 각 line의 요소를 가져와 floor배열에 저장을 합니다.

 

그리고 35번째 줄부터 모든 위치에 대해 DFS를 수행하는데, 방문하지 않은 위치가 있다면 DFS함수를 호출하여 나무판자의 수를 구합니다

 

 

DFS함수를 선언해 줍니다. 

 

인자로 받은 x, y 즉 현재 위치를 방문 처리해 주고, 현재 위치의 바닥 장식을 now로 저장을 합니다.

 

 -는 가로로 연결된 장식을 나타내고, |는 세로로 연결된 장식을 나타냅니다. 따라서 DFS 탐색을 할 때, -는 가로 방향(y축)으로 탐색하고, |는 세로 방향(x축)으로 탐색해야 합니다.

 

• 가로로 연결된 장식 (-)
  • -는 가로로 연결된 장식을 나타내므로, 같은 행에서 오른쪽으로 계속 연결되어 있을 수 있습니다.
    따라서 -를 탐색할 때는 현재 위치 (x, y)에서 오른쪽 위치 (x, y+1)으로 이동하며 탐색합니다.
• 세로로 연결된 장식 (|)
  • |는 세로로 연결된 장식을 나타내므로, 같은 열에서 아래쪽으로 계속 연결되어 있을 수 있습니다.
    따라서 |를 탐색할 때는 현재 위치 (x, y)에서 아래쪽 위치 (x+1, y)으로 이동하며 탐색합니다.

따라서 오른쪽으로 이동(-)할 수 있는지 확인 (범위를 벗어나지 않고, 다음 위치가 '-'이며, 방문하지 않은 경우)하고, 이동할 수 있다면 이동하고, 아래쪽으로 이동(|)할 수 있는지 확인 (범위를 벗어나지 않고, 다음 위치가 '|'이며, 방문하지 않은 경우)하고 이동합니다.

 

---

문제의 이해를 돕기 위해 가상의 예제와 DFS의 탐색 과정을 그림으로 설명하겠습니다. 예제를 다음과 같이 가정해 보겠습니다

3 4
- - | -
| - | -
- - - -

1. 초기 상태

초기 상태에서 바닥 장식과 방문 배열은 다음과 같습니다

바닥 장식 (floor):
- - | -
| - | -
- - - -

방문 배열 (visited):
F F F F
F F F F
F F F F

2. 첫 번째 DFS 탐색 시작 (0, 0)

첫 번째 위치 (0, 0)에서 DFS를 시작합니다. 이 위치는 -이고, 가로로 연결된 모든 -을 방문합니다.

바닥 장식 (floor):
- - | -
| - | -
- - - -

방문 배열 (visited):
T T F F
F F F F
F F F F

3. 다음 DFS 탐색 시작 (0, 2)

위치를 계속 순회하다가 (0, 2)에서 DFS를 시작합니다. 여기서는 |이고, 세로로 연결된 모든 |을 방문합니다.

바닥 장식 (floor):
- - | -
| - | -
- - - -

방문 배열 (visited):
T T T F
F F T F
F F F F

4. 다음 DFS 탐색 시작 (0, 3)

위치를 계속 순회하다가 (0, 3)에서 DFS를 시작합니다. 여기서는 -이고, 가로로 연결된 모든 -을 방문합니다.

바닥 장식 (floor):
- - | -
| - | -
- - - -

방문 배열 (visited):
T T T T
F F T F
F F F F

5. 다음 DFS 탐색 시작 (1, 0)

위치를 계속 순회하다가 (1, 0)에서 DFS를 시작합니다. 여기서는 |이고, 세로로 연결된 모든 |을 방문합니다.

바닥 장식 (floor):
- - | -
| - | -
- - - -

방문 배열 (visited):
T T T T
T F T F
F F F F

6. 다음 DFS 탐색 시작 (1, 1)

위치를 계속 순회하다가 (1, 1)에서 DFS를 시작합니다. 여기서는 -이고, 가로로 연결된 모든 -을 방문합니다.

바닥 장식 (floor):
- - | -
| - | -
- - - -

방문 배열 (visited):
T T T T
T T T F
F F F F

7. 다음 DFS 탐색 시작 (2, 0)

위치를 계속 순회하다가 (2, 0)에서 DFS를 시작합니다. 여기서는 -이고, 가로로 연결된 모든 -을 방문합니다.

바닥 장식 (floor):
- - | -
| - | -
- - - -

방문 배열 (visited):
T T T T
T T T F
T T T T

 

이 과정을 통해

• 첫 번째 나무판자: (0,0) - - 
• 두 번째 나무 판자: (0,2) | 
• 세 번째 나무 판자: (0,3) - 
• 네 번째 나무 판자: (1,0) | 
• 다섯 번째 나무 판자: (1,1) - 
• 여섯 번째 나무 판자: (2,0) - - - -

총 6개의 바닥 장식을 찾았습니다.

---

전체 코드

 

 

 

참고❗️

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