[Python_DFS&BFS] 백준 1987번 : 알파벳

1. 문제

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

1987번: 알파벳

 

 

 

2. 풀이과정

방법 1) DFS 이용

- Python 시간 초과, PyPy로 제출

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [input() for _ in range(n)]
visited = [False]*26

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

result = 0
def dfs(g, v, x, y, c):
  global result
  result = max(c, result)

  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0<=nx<n and 0<=ny<m and not v[ord(g[nx][ny])-65]:
      v[ord(g[nx][ny])-65] = True
      dfs(g, v, nx, ny, c+1)
      v[ord(g[nx][ny])-65] = False #백트래킹시 방문 취소
  return True

visited[ord(graph[0][0])-65] = True
dfs(graph, visited, 0, 0, 1)#시작점 포함해서 c=1로 시작
print(result)

 

 

방법 2) BFS 이용 & 큐를 집합으로 사용

(사실상, 여기서는 큐를 사용하지 않음. 이해하기 쉽게 하기 위해 '큐'라는 용어를 사용)

- 큐를 집합으로 사용하는 이유

1) 같은 위치에 같은 문자열을 가진 상황을 중복해서 확인할 필요없으니, 같은 값은 같은 객체로 취급하는 집합 자료형을 사용한다.

2) 여기서는 큐의 특성인 first-in, first-out을 지킬 필요가 없다. 각 칸의 상황을 위치와 함께 저장하고 있기 때문에 어떤 순서로 확인하던지 가능한 경우 전체를 완전 탐색할 수 있다.

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [input().rstrip() for _ in range(n)]
#오른쪽 개행 삭제
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def bfs(g):
  result = 1
  q = set()
  #현재 위치 x, y 지금까지 지나온 알파벳 문자열로 저장
  q.add((0, 0, graph[0][0]))
  
  while q and result!=26:
    x, y, road = q.pop()
    result = max(result, len(road))

    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0<=nx<n and 0<=ny<m and g[nx][ny] not in road:
        q.add((nx, ny, road+g[nx][ny]))
  print(result)

bfs(graph)