1. 문제

문제 설명

내 여자친구가 코딩을 꽤하는데 이 문제는 DFS 문제 중 쉬운 편이라고 한다
그러나 나는 DFS에 대한 개념이 부족해서 어떻게 풀어야할지... 도저히 방벙이 떠오르지 않았다
그래서 여자친구에게 SOS를 요청했고 DFS문제를 재귀형식으로 푸는 방법과 backtracking을 적용하는 방법을 배웠다! (감사합니다❤)

본격적으로 문제 설명을 시작해보자면
알파벳을 값으로 가지는 2차원배열(board)이 주어지고 우리가 찾으려는 문자열(input)을 입력 받는다
그다음 board에서 한 칸씩 이동하면서 input과 같은 문자열을 만들어 낼 수 있는지를 확인하는 것이다

제한사항

• board에서 이동할 때는 현재 위치에서 가로, 세로로만 가능하다
• 왔던 곳을 되돌아가지 못한다

입출력 예

board = [["A", "B", "C", "E"], [ "S", "F", "C", "S"], [ "A", "D", "E", "E"]]
input = "ABCCED”
=> output = true

2. 아이디어

• 전역변수로 설정할 것들
  • 현재 input에서 몇 번째에 커서가 있는지 나타내는 int형 변수
  • output을 나타내는 bool형 변수
  • 방문여부를 나타내는 2차원배열
  • 총 만들어지는 방법의 가짓수를 기록하는 int형 변수
• input의 첫번째 글자와 같은 글자를 board에서 찾게되면 해당 위치에서 DFS 함수를 호출
• board에서 이동할 수 있는 방향(상,하,좌,우)를 행과 열을 각각 배열 형태로 표현
• 같은 글자가 발견된다면 해당 위치에서 재귀적으로 DFS 함수를 호출

3. 코드

public class searchingWord {

    public static int index = 0;//input string에서 몇 번째 인덱스가 타겟인지 표시
    public static boolean output = false;
    public static int[][] visited;
    public static int count = 0;

    public static void dfs(int row, int col, String[][] board, String[] input, int idx){



        //움직이는 방향을 배열로 표시 {우,하,좌,상}
        int[] moveRow = {0,1,0,-1};
        int[] moveCol = {1,0,-1,0};
        //다 찾았으면 함수 종료
        if(idx >= input.length){
            count++;
            index = 0;
            return;
        }
        //move
        for(int i = 0; i < 4; i++){
            row += moveRow[i];
            col += moveCol[i];
            //이동 영역 제한 - 다음번 반복으로 이동
            if(col<0 || col >= board[0].length || row<0 || row>=board.length) {
                row -= moveRow[i];
                col -= moveCol[i];
                continue;
            }
            //이미 방문한 곳에 방문했다면
            if(visited[row][col] == 1) {
                row -= moveRow[i];
                col -= moveCol[i];
                continue;
            }
            //같은 글자가 나왔다면
            if(board[row][col].equals(input[index])){
                visited[row][col] = 1;
                index++;
                dfs(row, col, board, input, index);
                visited[row][col] = 0;//백트레킹
            }
            //같은 것을 못 찾았을 때(위 if문에 하나도 해당이 안될 때) 이동한만큼을 다시 빼주어야한다(이것때문에 계속 오류가 났었다)
            else{
                row -= moveRow[i];
                col -= moveCol[i];
            }
        }
    }

    public static boolean solution(String[][] board, String[] input){

        visited = new int[board.length][board[0].length];//방문여부를 기록

        for(int i = 0; i < board.length;i++){
            for(int j = 0; j < board[i].length;j++){
                //input의 첫 글자와 같은 글자를 찾아서
                if(index >= input.length) break;
                if(board[i][j].equals(input[index])){
                    visited[i][j] = 1;//방문했다고 기록하고
                    index++;
                    dfs(i, j, board, input, index);//dfs 함수 호출
                }
                index = 0;
            }
        }
        if(count>0) output = true;

        return output;
    }

    public static void main(String[] args) {

       String[][] board = {{"A","B","C","E"},{"S","F","C","S"},{"A","D","E","E"}};
       String input = "ABCB";
       String[] arr_input = input.split("");

       System.out.println(solution(board, arr_input));
    }
}

4. end...

이게 쉬운 문제란다 허허허 어이가 없다...🤦‍♂️