[백준][C#] 1987 알파벳 - 골드4

문제 보기

https://www.acmicpc.net/problem/1987

1987번: 알파벳

 

문제                           

 

입력                          

 

출력                          

 

풀이방법                 

https://mountain-noroo.tistory.com/16

[백준][C#] 15649 N과 M (1) - 실버3

 

위 포스팅과 거의 동일한 풀이를 사용할 수 있는 백트래킹 문제이다.

저번 문제에서는 방문한 index를 true로 바꾸어주고 DFS 진입, 다음 수열을 작성하기 위해 다시 false로 바꾸어 주었는데

이번에는 어떤 알파벳이 쓰였는지 찾아와 true로 바꾸어주는 정도 차이다.

그리고 계속 최댓값을 갱신해 주면 끝!

 

            bool[] visited = new bool[26];
            // 상하좌우의 x,y값
            int[] addX = { 1, -1, 0, 0 };
            int[] addY = { 0, 0, 1, -1 };

            int max = 0;
            // 말의 시작 위치는 true로 바꾸어준다.
            // 이렇게 char를 사용하는 경우 첫 문자인 'A'를 빼주면 된다.
            visited[chars[0, 0] - 'A'] = true;
            // DFS 진입. 이미 시작 위치에 있으니 count는 1
            DFS(0, 0, 1);

            void DFS(int x, int y, int count)
            {
            	// 매번 max값 갱신하기
                max = Math.Max(max, count);

                // 상하좌우 탐색하기
                for (int i = 0; i < 4; i++)
                {
                    // x, y 값이 보드게임 판 안에 있을 때
                    if(x + addX[i] < C && x + addX[i] >= 0 && y + addY[i] < R && y + addY[i] >= 0)
                    {
                        // 알파벳의 인덱스 구하기
                        int index = chars[x + addX[i], y + addY[i]] - 'A';
                        // 방문하지 않은 알파벳이라면
                        if (!visited[index])
                        {
                            // 방문 여부를 true로 바꾸고
                            visited[index] = true;
                            // 다음 칸으로 진입합니다.
                            DFS(x + addX[i], y + addY[i], count + 1);
                            // DFS에서 빠져나온 시점에서, 다음 경우의 수를 준비하기 위해
                            // 방문 여부를 다시 false로 바꾸어 줌.
                            visited[index] = false;
                        }
                    }
                }
            }

 

 

전체 코드 보러가기

https://github.com/MetroDefro/BackjoonCodingTest/tree/main/%EB%B0%B1%EC%A4%80/Gold/1987.%E2%80%85%EC%95%8C%ED%8C%8C%EB%B2%B3