[ 백준 1987 해설 ] ( python ) 알파벳

 

📚 알파벳

 

문제

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

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

 

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

 

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

 

예제 입력 1 복사

2 4
CAAB
ADCB

예제 출력 1 복사

3

예제 입력 2 복사

3 6
HFDFFB
AJHGDH
DGAGEH

예제 출력 2 복사

6

예제 입력 3 복사

5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

예제 출력 3 복사

10

 

 

✍ 접근

• BFS
• DFS로 탐색할까 생각했지만.. 조금 더 익숙한 BFS를 사용했다
• 다른 사람의 코드를 보고 deque가 아닌 set을 이용해서 풀이했다 😌

 

 

 

 

정답코드

# ✨ 입력
import sys
input = sys.stdin.readline
R,C = map(int,input().split())
board = [list(input()) for _ in range(R)]

# ✨ 준비
dx = [-1,0,1,0]
dy = [0,1,0,-1]

# ✨ BFS
def BFS(x,y):
    answer =1
    dq = set([])
    dq.add((x,y,board[x][y]))
    while dq:
        xx,yy,visited = dq.pop()
        for i in range(4):
            nx = xx+dx[i]
            ny = yy+dy[i]
            if 0<=nx<R and 0<=ny<C and board[nx][ny] not in visited:
                dq.add((nx,ny,visited+board[nx][ny]))
                answer = max(answer,len(visited)+1)
    print(answer)
        
BFS(0,0)

 

해설

입력

• 문제에서 나온 값을 입력받는다

준비

• dx와 dy를 입력해준다

BFS

• BFS 함수를 이용하는데 몇 가지 신경써야 하는 부분이 있다
  🚨 첫 번 째는 deque가 아닌 set 자료구조를 이용했다는 것
  🚨 두 번 째는 visited를 dq 안에 삽입하고, 최대 방문 칸 개수를 셀 때 visited의 개수를 세었다는 점이다
  
  
• 우선 현재 위치해있는 0,0 칸도 한 칸으로 따지기 때문에 answer =1 을 해준다
• dq를 set으로 초기화하고 x,y,board[x][y]를 넣어준다. 
  
• 4방위를 돌아준 후 만약 board[nx][ny]가 visited에 없을 때
  => 아직 방문하지 않은 알파벳일 때
• dq에 add해준다 ✨ 자료구조가 set이기 때문에 append가 아닌 add이다
• 그리고 answer을 갱신해준다(1을 더하는건 0,0도 한 칸으로 따지기 때문에)

 

 

 

⭐ 배움

• BFS로 풀기 힘든 문제라고 생각했는데 생각을 조금만 더 유연하게 가지면 풀 수 있는 문제였다. 
• deque 대신 set을 이용한 것과
• visited를 dq에 넣고 방문 알파벳 개수를 구할 때 visited 안의 알파벳 개수를 카운팅한것도 좋았다