[백준/Python] 1987번 - 알파벳

문제

백준 1987번 - 알파벳

해결과정

• DFS로 풀기
• (0,0)부터 시작한다.
• 상하좌우를 확인한다.
  • 0 <= nx < r and 0 <= ny < c: 범위 안에 있고
  • 지나갔던 알파벳이 아니라면
  • 알파벳 집합에 넣고 dfs를 돈다.
  • 재귀를 빠져나오면 넣었던 알파벳을 다시 뺀다 = 백트래킹

시행착오

• 최대의 칸 수가 아니다.. -> dfs 파라미터 수정, alpha.pop() 해주기 -> 백트래킹

import sys

r,c = map(int,sys.stdin.readline().split())
graph = []

for _ in range(r):
  graph.append(list(sys.stdin.readline().strip()))

print(graph)
dx = [-1,1,0,0]
dy = [0,0,1,-1]
visited = [[False] * c for _ in range(r)]
alpha = []
cnt = 0

def dfs(x,y):
  global cnt
  visited[x][y] = True
  alpha.append(graph[x][y])
  cnt += 1
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0 <= nx < r  and 0 <= ny < c:
      if not visited[nx][ny]:
        if graph[nx][ny] not in alpha:
          visited[nx][ny] = True
          dfs(nx,ny)
          

dfs(0,0)
print(cnt)

• 시간초과 -> 리스트를 집합으로 바꾸면 pypy3 통과

import sys

r,c = map(int,sys.stdin.readline().split())
graph = []

for _ in range(r):
  graph.append(list(sys.stdin.readline().strip()))

# 상하좌우
dx = [-1,1,0,0]
dy = [0,0,1,-1]

alpha = []
ans = 0

def dfs(x,y,cnt):
  global ans
  ans = max(ans, cnt)
  alpha.append(graph[x][y])
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0 <= nx < r  and 0 <= ny < c:

        if graph[nx][ny] not in alpha:
			
          dfs(nx,ny,cnt+1)

          alpha.pop()
          

dfs(0,0,1)
print(ans)

Pypy3 풀이

import sys

r,c = map(int,sys.stdin.readline().split())
graph = []

for _ in range(r):
  graph.append(list(sys.stdin.readline().strip()))

# 상하좌우
dx = [-1,1,0,0]
dy = [0,0,1,-1]

# 지나간 알파벳을 담는 집합
alpha = set()

ans = 0

def dfs(x,y,cnt):
  global ans
  ans = max(ans, cnt)
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    
    # 범위 안에 있다면
    if 0 <= nx < r  and 0 <= ny < c:
      # 지나갔던 알파벳이 아니라면
      if graph[nx][ny] not in alpha:
        # 넣고
        alpha.add(graph[nx][ny])
        dfs(nx,ny,cnt+1)
        # 다시 빼고
        alpha.remove(graph[nx][ny])
          
alpha.add(graph[0][0])
dfs(0,0,1)

print(ans)