백준 1987 - 알파벳

백준 1987 문제 바로가기

풀이

• 좌측 상단 (0, 0)에서 상하좌우로 이동할 때 알파벳을 중복으로 방문하지 않고 최대한 이동할 수 있는 칸의 개수가 몇 개인지 구하는 문제
• 26개의 대문자 알파벳을 사용했는지 확인하기 위한 배열을 두고, 임의의 위치 (r, c)를 방문할 때 chk[field[r][c]] 값이 false인 경우에만 방문하고 true로 변경해준다.
• DFS를 사용하여 이동할 수 있는 위치를 탐색하되, 더 이상 탐색할 수 없는 위치인 경우에는 다시 방문할 수 있도록 해야한다.(백트래킹)

func dfs(r, c, len int) {
   	visited[r][c] = true // 현재 위치를 방문한 것으로 체크
	chk[field[r][c]-'A'] = true // use
    ... (이동할 수 있는 인접한 위치를 방문)
	chk[field[r][c]-'A'] = false // unuse
	visited[r][c] = false // 현재 위치를 방문하지 않은 것으로 체크
}

소스 코드

package main

import (
	"bufio"
	"fmt"
	"os"
)

var dr = [...]int{-1, 1, 0, 0}
var dc = [...]int{0, 0, -1, 1}

var R, C int
var field [20]string
var visited [20][20]bool
var chk [26]bool
var ans int

func isValid(r, c int) bool {
	return 0 <= r && r < R && 0 <= c && c < C
}

func dfs(r, c, len int) {
	if ans < len {
		ans = len
	}
	visited[r][c] = true
	chk[field[r][c]-'A'] = true // use
	for d := 0; d != 4; d++ {
		nr := r + dr[d]
		nc := c + dc[d]
		if isValid(nr, nc) && !visited[nr][nc] && !chk[field[nr][nc]-'A'] {
			dfs(nr, nc, len+1)
		}
	}
	chk[field[r][c]-'A'] = false // unuse
	visited[r][c] = false
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)

	fmt.Fscanln(reader, &R, &C)
	for r := 0; r < R; r++ {
		fmt.Fscanln(reader, &field[r])
	}
	dfs(0, 0, 1)

	fmt.Fprintln(writer, ans)
	writer.Flush()
}