문제
형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나무 판자는 크기 1의 너비를 가졌고, 양수의 길이를 가지고 있다. 기훈이 방은 직사각형 모양이고, 방 안에는 벽과 평행한 모양의 정사각형으로 나누어져 있다.
이제 ‘-’와 ‘|’로 이루어진 바닥 장식 모양이 주어진다. 만약 두 개의 ‘-’가 인접해 있고, 같은 행에 있다면, 두 개는 같은 나무 판자이고, 두 개의 ‘|’가 인접해 있고, 같은 열에 있다면, 두 개는 같은 나무 판자이다.
기훈이의 방 바닥을 장식하는데 필요한 나무 판자의 개수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 방 바닥의 세로 크기N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 M개의 문자가 주어진다. 이것은 바닥 장식 모양이고, '-‘와 ’|‘로만 이루어져 있다. N과 M은 50 이하인 자연수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
예제 입력
6 9
-||--||--
--||--||-
|--||--||
||--||--|
-||--||--
--||--||-
예제 출력
31
내가 했던 풀이 방법
-
벽지를 입력받을 2차원 배열과 해당 벽지를 counting했음을 표시하는 visited 2차원 배열을 만들어준다. (visited 배열의 요소를 전부 false로 초기화해준다.)
-
현재 위치에 벽지를 counting했을 경우(visited가 true일 때)에는 무시한다.
-
현재 벽지가 '-'일 때, 다음 행이 '-'일 경우는 같은 벽지이므로, '|' 벽지가 나오거나, 마지막 행이 되기 전까지 행을 1씩 증가해주면서 해당 위치의 visited를 true로 바꾸어준다. '|' 벽지이거나, 마지막 행일 경우 나무 판자의 수를 1 증가시켜준다.
-
현재 벽지가 '|'일 때, 다음 열이 '|'일 경우는 같은 벽지이므로, '-'가 나오거나, 마지막 열이 되기 전까지 열을 1씩 증가해주면서 해당 위치의 visited를 true로 바꾸어준다. '-' 벽지이거나, 마지막 열일 경우 나무 판자의 수를 1 증가시켜준다.
-
모든 벽지를 다 counting했을 때의 number를 출력한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int height = Integer.parseInt(input[0]);
int width = Integer.parseInt(input[1]);
String wall;
int number = 0;
char[][] walls = new char[height][width];
boolean[][] visited = new boolean[height][width];
for (int i=0; i <height; i++) {
Arrays.fill(visited[i], false);
}
for(int i=0; i<height; i++) {
wall = br.readLine();
for(int j=0; j<width; j++) {
walls[i][j] = wall.charAt(j);
}
}
char current;
int move_index;
for(int i=0; i<height; i++) {
for(int j=0; j<width; j++) {
if(visited[i][j]) continue;
current = walls[i][j];
if(current=='-') {
move_index = j+1;
while(true) {
if(move_index==width) {
number++;
break;
}
if (walls[i][move_index]=='|') {
number++;
break;
} else {
visited[i][move_index] = true;
move_index++;
}
}
} else {
move_index = i+1;
while(true) {
if(move_index==height) {
number++;
break;
}
if (walls[move_index][j]=='-') {
number++;
break;
} else {
visited[move_index][j] = true;
move_index++;
}
}
}
}
}
System.out.print(number);
}
}
회고
요즘 문제를 이해 못하는 경우가 늘어나는 것 같다. "두 개의 ‘-’가 인접해 있고, 같은 행에 있다면, 두 개는 같은 나무 판자이고"라는 문장을 보고 최대 2개까지가 하나의 나무 판자일거라 생각했는데 그렇게 계산하니 예제들이 전부 잘못된 출력을 가졌다. 하나의 경우의 수로 인접한 모든 '-'는 하나의 나무 판자라는 것이었는데 이렇게 계산하니 모두 제대로 출력이 되었다. (문제가 암만봐도 모호하단 말이지...) 사실 문제를 이해 못해서 문제 이해를 위해 검색을 하다가 DFS로 풀이하라는 스포당했기 때문에 좀 더 일찍 풀 수 있었던 게 아니었을까... 싶긴하다. 그래도 DFS로 풀이해야 한다는 말만 듣고도 이렇게 코드를 바로 짤 수 있다는 게 발전했다는 거 아닌가 싶기도 하고...!!!!!!
