문제 내용은 입력으로 행과 열의 갯수를 받고 이후 -, |로 이루어진 문자열을 받은 뒤, – 와 | 의 갯수를 출력해줘야 하는데 여기서 -가 가로로 연결되어 있을 경우에는 —- 이렇게 4개여도 한개로 치고 |는 세로로 연결되어 있을 경우 1개로 치는데 세로로 쓰기에는 좀 난감하니 생략하고 -|-|– 이러면 연결되어 있는 -를 생각해보면 5를 출력해야 한다
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int row, col;
static char[][] arr;
static boolean[][] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] rowCol = br.readLine().split(" ");
row = Integer.parseInt(rowCol[0]);
col = Integer.parseInt(rowCol[1]);
arr = new char[row][col];
visited = new boolean[row][col];
for (int i = 0; i < row; i++) {
String s = br.readLine();
for (int j = 0; j < col; j++) {
arr[i][j] = s.charAt(j);
}
}
int count = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (visited[i][j]) {
continue;
} else if (arr[i][j] == '-') {
dfs(i, j, true);
} else {
dfs(i, j, false);
}
count++;
}
}
System.out.println(count);
}
public static void dfs(int i, int j, boolean horizontal) {
visited[i][j] = true;
if (horizontal) {
j++;
if (j < col && arr[i][j] == '-') {
dfs(i, j, true);
}
} else {
i++;
if (i < row && arr[i][j] == '|') {
dfs(i, j, false);
}
}
}
}문제를 풀어보자면 배열에 입력받은 내용을 모두 넣어준 뒤 dfs를 사용해서 문제를 풀어줘야 하는데 dfs라고 해서 당황할 필요는 없고 for 문을 돌려주려면서 -일 경우에는 우측으로 한 칸씩 이동하면서 다음 값도 -면 내부에서 dfs를 계속 호출하면서 visited를 true로 놓아주면
처음 한 번만 호출해도 인접한 우측 열이 -인 항목은 모두 visited가 true로 처리되고, 한 번만 호출한 후 내부에서 또 호출하는 식으로 같은 값을 visited true 처리하기 때문에, 재방문할 일이 없고 이후 count++ 를 통해 횟수를 늘려주는 식이다
설명은 – 기준으로 설명했지만 | 는 열 대신 행을 visited 처리하게 변경하면 구조는 동일하고, 마지막으로 count값을 출력해주면 끝이 난다
Leave a Reply