[백준(BOJ)] 1987번 : 알파벳 - PYTHON[파이썬]

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

1987번: 알파벳

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색
• 백트래킹

 

---

 

⊙ 문제 접근 과정

 

bfs를 사용해 문제를 풀었다.

 

조건을 통해 알파벳이 탐색하지 않았고 범위 안에 있다면 탐색을 추가한다.

계속해서 반복하여 answer의 최댓값을 갱신해준다.

 

처음에 dfs로 문제를 풀어봤는데 pypy로 해도 시간 초과가 나서 bfs로 풀었다.

 

 

---

 

⊙ 문제 풀이

 

import sys

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

dx = [0,0,1,-1]
dy = [1,-1,0,0]

def bfs(x,y):
    global answer
    q = set([(x,y,l[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 (l[nx][ny] not in ans)):
                q.add((nx,ny,ans+l[nx][ny]))
                answer = max(answer, len(ans)+1)

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

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!