BOJ 문제 링크 : https://www.acmicpc.net/problem/1987

 

1987번: 알파벳

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으

www.acmicpc.net

R * C 크기의 표 모양의 보드가 알파벳으로 이뤄진채 주어진다.

말은 보드의 좌측 상단에서 시작해 상하좌우 4방향으로 한 칸씩 이동 가능하다.

단, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과 달라야한다.

이때 말이 최대한 몇칸을 지날 수 있는지 구하는것이 문제이다.

 

해당 문제는 dfs를 이용하여 문제를 풀 수 있다.

여기서 중요한점은 이미 지나온 경로에 있는 알파벳을 따로 저장하여 앞으로의 경로와 비교해야 한다는 것이다.

나는 지나온 알파벳을 비트마스크 형태로 저장하여 다음 경로의 알파벳과 bit단위 비교를 하여 다음 경로가 유효한지 판단하였다.

코드 원본 : https://github.com/sbl133/BOJ/blob/main/%231987.cpp

 

GitHub - sbl133/BOJ

Contribute to sbl133/BOJ development by creating an account on GitHub.

github.com

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

+ Recent posts