[BaekJoon] 1987 알파벳

yunan·2020년 9월 28일
0
post-thumbnail

🔦 문제 링크

✍️ 나의 풀이


  • DFS문제 처럼 풀면 된다.
  • Visited 보다 문자 자체에 표시를 해두는 것이 더 좋다.

<순서>
1. 문자를 숫자로 치환해둔다.
2. 치환한 숫자를 이용해 최대로 갈 수 있는 길을 찾는다.

🛠 나의 코드


import sys
r, c = map(int,sys.stdin.readline().split())
arr = [ list(map(lambda x: ord(x) - ord('A'),sys.stdin.readline().strip())) for _ in range(r)]
#print(arr)
mx = -1
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def dfs(x, y, index):
    global mx
    mx = max(index, mx)

    for k in range(4):
        tx = x + dx[k]; ty = y + dy[k]
        if 0 <= tx < c and 0 <= ty < r:
            tmp = arr[ty][tx]
            if ch[tmp] == 0:
                #print(arr[ty][tx])
                ch[tmp] = 1
                dfs(tx, ty, index+1)
                ch[tmp] = 0

ch = [0]*(r*c)

ch[arr[0][0]] = 1
dfs(0, 0, 1)
print(mx)

✍️ BFS 풀이


  • 이 문제는 최대 길이를 구하는 문제여서 그런지 DFS가 더 빠르다.
  • settuple을 이용해 집합을 구성했다.
  • set에 들어간 값은 다시 선택될 수 없다.

🛠 BFS 코드


def BFS(x, y):
    global answer
    q = {(x, y, board[x][y])}

    while q:
        x, y, ans = q.pop()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < R and 0 <= ny < C and board[nx][ny] not in ans:
                q.add((nx,ny,ans + board[nx][ny]))
                answer = max(answer, len(ans)+1)


R, C = map(int, sys.stdin.readline().split())
board = [[sys.stdin.readline().strip()] for _ in range(R)]

answer = 1
BFS(0, 0)
print(answer)

📝 정리


  • BFS , DFS 풀이 방식에 대해 기억해두자.

🎈 참고


profile
Go Go

0개의 댓글