BOJ [알파벳]

2022-03-20

문제보기

풀이

r = 5
c = 5

arr = [list('IEFCJ'),list('FHFKC'),list('FFALF'),list('HFGCF'),list('HMCHH')]
now_str = set([])
count = 0
temp_count = 0
visited=[[False for _ in range(c)]for _ in range(r)]

def dfs(x,y):

    global count,temp_count,now_str,arr,r,c
    
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]

    if x<0 or x>=c or y<0 or y>=r:
        return
    
    if arr[y][x] in now_str or visited[y][x]:
        if visited[y][x]:
            print('already visited')
            
        else:
            print('alpha bet joongbok')
        return

    visited[y][x] = True
    temp_count += 1
    count = max(count,temp_count)

    now_str.add(arr[y][x])
    for i in range(4):
        dfs(x+dx[i],y+dy[i])

    now_str.remove(arr[y][x])
    temp_count -= 1
    visited[y][x] = False

dfs(0,0)

print(count)

주목해서 볼 부분은 다음이다.

	visited[y][x] = True
    temp_count += 1
    count = max(count,temp_count)

    now_str.add(arr[y][x])
    
    for i in range(4):
        dfs(x+dx[i],y+dy[i])

    now_str.remove(arr[y][x])
    temp_count -= 1
    visited[y][x] = False

visited[] 는 방문한 칸을 다시 방문하지 않기 위함이고 now_str{}은 이미 지나온 알파벳을

다시 지나가지 않기 위해서 설정해 주었다.

동서남북 방향으로 재귀함수를 통해 진행한다.

x,y 가 범위를 넘어가거나, 해당 칸이 이미 방문한 칸이거나, 해당 칸의 알파벳이 이미 지나온

알파벳이면 return 으로 재귀를 빠져나온다. 동서남북으로 다 진행한 뒤에는 모든 설정값을 방문

이전으로 되돌리고 함수를 빠져나온다.