백준 7662번
https://www.acmicpc.net/problem/7662

문제

---

생각하기

---

• 일반 DFS,BFS 탐색에서 가로와 세로를 분리해서 생각한다.
• 붙어있는 것들은 하나의 판자로 친다

동작

		int result = 0;
		// 가로 모양 타일 탐색
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(!visit[i][j] && arr[i][j] == '-') {
					DFS(i, j, 0, 2, '-');
					result++;
				}
			}
		}
		

		// 세로
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if(!visit[j][i] && arr[j][i] == '|') {
					DFS(j, i, 2, 4, '|');
					result++;
				}
			}
		}

결과값을 받은 result생성

가로 '-' 모양으로 된 타일을 먼저 탐색 DFS탐색을 하기 위해서 매개 변수를 좌표 i, j를 주고,

방향탐색을 위한 배열 dirX, dirY의 인덱스값인 0, 2를 준다.

이렇게 하면, 가로 탐색을 위해 좌 우를 배열에서 먼저줬을 때, dirX, dirY의 0, 1, 인덱스 값만 불러오면 되기 때문에 0, 2의 인덱스로 준다. 그리고 나무 판자 모양인 '-'를 매개 변수로 준다.

매개 변수만 추가해주고, 가로 세로를 위한 약간의 변경 해주면 기존의 DFS틀을 이용해서 2가지 조건을 탐색할 수 있다.

for(int i=idxStart; i<idxEnd; i++) {

dirX 와 dirY의 탐색을 가로 세로로 분리하기 위해 DFS에서 for문을 매개변수 idxStart, idxEnd로 주고 돌린다.

코드

---

Java

import java.util.*;
import java.io.*;

// 기훈이의 방 바닥을 장식하는데 필요한 나무 판자의 개수를 출력하는 프로그램을 작성하시오.
// -는 인접, 같은 행 , |는 인접 같은 열

public class Main {
	static int N;
	static int M;
	static char arr[][];
	static boolean visit[][];
	static int nowX; static int nowY;
	static int dirX[] = {0, 0, -1, 1};
	static int dirY[] = {-1, 1, 0, 0};
	
	static int result = 0;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		arr = new char[N][M];
		visit = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			String temp = br.readLine();
			for (int j = 0; j < M; j++) {
				arr[i][j] = temp.charAt(j);
			}
		}

		int result = 0;
		// 가로 모양 타일 탐색
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(!visit[i][j] && arr[i][j] == '-') {
					DFS(i, j, 0, 2, '-');
					result++;
				}
			}
		}
		

		// 세로
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if(!visit[j][i] && arr[j][i] == '|') {
					DFS(j, i, 2, 4, '|');
					result++;
				}
			}
		}

		System.out.println(result);
	} // End of main

	private static void DFS(int x, int y, int idxStart, int idxEnd, char ch) {
		visit[x][y] = true;
		
		for(int i=idxStart; i<idxEnd; i++) {
			nowX = dirX[i] + x;
			nowY = dirY[i] + y;
			
			if(range_check() && !visit[nowX][nowY] && arr[nowX][nowY] == ch) {
				DFS(nowX, nowY, idxStart, idxEnd, ch);
			}
		}
	} // End of DFS
	
	private static boolean range_check() {
		return nowX >= 0 && nowX < N && nowY >= 0 && nowY < M;
	} // End of range_check
} // End of Main class

Kotlin

import java.util.*
import java.io.*

private var N = 0; private var M = 0
private lateinit var arr : Array<CharArray>
private lateinit var visit: Array<BooleanArray>
private val dirX = arrayOf(0, 0, -1, 1)
private val dirY = arrayOf(-1, 1, 0, 0)

private var nowX = 0; private var nowY = 0
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt(); M = st.nextToken().toInt();

    arr = Array(N){CharArray(M)}
    visit = Array(N){BooleanArray(M)}
    for(i in 0 until N) {
        val temp = br.readLine()
        for(j in 0 until M) {
            arr[i][j] = temp[j]
        }
    }

    var result = 0
    // 가로 탐색
    for(i in 0 until N) {
        val temp = br.readLine()
        for(j in 0 until M) {
            if(!visit[i][j] && arr[i][j] == '-') {
                DFS(i, j, 0, 2, '-')
                result++
            }
        }
    }

    // 세로 탐색
    for(i in 0 until M) {
        val temp = br.readLine()
        for(j in 0 until N) {
            if(!visit[j][i] && arr[j][i] == '|') {
                DFS(j, i, 2, 4, '|')
                result++
            }
        }
    }

    print(result)
} // End of main

private fun DFS(x : Int, y : Int, idxStart : Int, idxEnd : Int, ch : Char) {
    visit[x][y] = true

    for(i in idxStart until idxEnd) {
        nowX = dirX[i] + x
        nowY = dirY[i] + y

        if(range_check() && !visit[nowX][nowY] && arr[nowX][nowY] == ch) {
            DFS(nowX, nowY, idxStart, idxEnd, ch)
        }
    }
} // End of DFS

private fun range_check() : Boolean {
    return nowX >= 0 && nowX < N && nowY >= 0 && nowY < M
} // End of range_check