백준 1987번: 알파벳

 

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

1987번: 알파벳

문제

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

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

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

 

 

 

---

처음 풀려고 했던 방법은..

alphabet=[] 리스트를 만들어서 지나갈 때마다 알파벳을 추가하고, 동서남북 탐색할 때에는 alphabet 리스트를 보고 갈지말지 결정하는 식으로 했다.

from collections import deque

r,c=map(int,input().split()) #세로r칸 가로c칸

board=[]#보드판
for i in range(r):
    board.append(list(map(str,input())))


visited=[[0]*c for i in range(r)] #방문기록할 배열
alphabet=[]

dx=[1,-1,0,0]
dy=[0,0,1,-1]
def bfs():
    queue=deque()
    queue.append((0,0))
    count=1 #지나온 칸 개수를 셀 count
    visited[0][0]=1 #방문표시
    alphabet.append(board[0][0]) #0,0 알파벳 기록
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx<0 or ny<0 or nx>=r or ny>=c:
                continue #보드를 벗어나는경우는 뺌
            if board[nx][ny] not in alphabet:
                alphabet.append(board[nx][ny]) #알파벳 기록
                visited[nx][ny]=visited[x][y]+1
                queue.append((nx,ny))


bfs()

result=0
for i in visited:
    result = max(result,max(i))
print(result)

근데 문제는..

 

bfs는 한 경로로 쭉 가는게 아니라 넓게 조금조금 가니까..

알파벳 리스트 하나를 이용해서 bfs를 돌려버리면

1번방법으로 갔던게 알파벳리스트에 추가되고 2번방법으로 가려고했더니만 1번방법할 때 알파벳 추가해놔서 못가고 이런일이 생기는거같음..

 

그래서 dfs로 풀어야하나? 생각했다

재귀 다 돌고나서 알파벳리스트를 초기화해준다거나 하는식으로 해보려했는데

 

bfs로 푸는 방법도 있을거같아서 찾아봤다

from collections import deque

r,c=map(int,input().split()) #세로r칸 가로c칸

board=[]#보드판
for i in range(r):
    board.append(list(map(str,input())))


visited=[[0]*c for i in range(r)] #방문기록할 배열
alphabet=[]

count=0
dx=[1,-1,0,0]
dy=[0,0,1,-1]
def bfs():
    queue=set()
    queue.add((0,0,board[0][0]))
    result=1 #지나온 칸 개수를 셀 count
    
    alphabet.append(board[0][0]) #0,0 알파벳 기록
    
    while queue:
        x,y,alphabets=queue.pop()
        result=max(result,len(alphabets))
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx<0 or ny<0 or nx>=r or ny>=c:
                continue #보드를 벗어나는경우는 뺌
            if board[nx][ny] not in alphabets:
                queue.add((nx,ny,alphabets + board[nx][ny]))
    return result


print(bfs())

 

우선은 queue=set()으로.. 집합으로 사용함. 그래서 append -> add, popleft -> pop 으로 바꿈..

이게 그냥 deque로 하면 중복되는게 생겨서 시간초과가 나는거같음

 

그러고..

queue에는 (x좌표,y좌표,지나오면서 밟은 알파벳string) 을 담을것임..

 

우선 문제에서 시작점은 (0,0)이라고 해놨으니까 queue.add((0,0,board[0][0])을 해준다.

중간 쭉 쭉 쭉 넘어가고

주변 칸 중 안밟았던 알파벳이 있을 때(= if board[nx][ny] not in alphabets:)

queue에 (nx, ny, 지나오면서 밟았던 알파벳들+다음칸 알파벳)을 해줌..

 

 

그럼 while문을 계속 돌면서..

알파벳 리스트를 관리할 필요 없이.. 각자 어떤 알파벳을 밟고 지나갔는지 다 기록이되고..

그렇게되면... 그 기록들 중에 가장 긴 걸 찾으면... 정답이 됨..;;

 

예시 입력이

3 6

HFDFFB

AJHGDH

DGAGEH

일 때

대충 큐에 들어가는 값들을 생각해보면..

 

(0,0,H)

(1,0,HA)

(0,1,HF)

(0,2,HFD)

(1,1,HFJ)

(1,1,HAJ)

(2,0,HAD)

 

뭐 이런식으로 쭉쭉 되는걸 알 수 있음... 해보면 대충 뭔소린지 감이옴

 

그래서 여기서 저 문자열의 최대길이를 찾으면 답이되는거~