코드

DFS - set 활용 (Pypy3 정답)

r, c = map(int, input().split())

graph = []

for _ in range(r):
    graph.append(list(input()))

# 방문한 알파벳을 담을 set
# list대신 set을 활용
tmp = set()    
    
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 최종 정답
answer = -float('inf')

def dfs(x, y, cnt):
    global answer
    
    # cnt를 dfs를 반복할 때마다 1씩 증가시킴
    # 확장된 알파벳 영역의 개수가 됨
    # 기존의 answer와 새로운 cnt 중 더 큰 값을 answer로 변경
    answer = max(answer, cnt)
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
    
        if nx < 0 or nx >= r or ny < 0 or ny >= c:
            continue

        # 다음 지점의 알파벳이 방문한 적 없다면
        if not graph[nx][ny] in tmp:
            
            # 백트래킹 수행
            # set에 넣음
            tmp.add(graph[nx][ny])
            
            # cnt+1을 한 후, dfs 수행
            dfs(nx, ny, cnt+1)
            
            # 다른 경로로 이동해야 하므로 set에서 알파벳 제거
            tmp.remove(graph[nx][ny])

# 시작점도 포함해야 하므로 설정            
tmp.add(graph[0][0])

dfs(0, 0, 1)

print(answer)

BFS - Python3 정답

r, c=map(int, input().split())

graph=[]

for i in range(r):
    graph.append(list(input()))
    
dx = [1,-1,0,0]
dy = [0,0,1,-1]

def bfs():
    
    # 최종 정답 변수
    answer = 1
    
    # set을 활용하여 중복 제거
    # 좌표 x, y 와 그 좌표의 알파벳을 set에 넣어줌
    q = set([(0, 0, graph[0][0])])

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

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= r or ny < 0 or ny >= c:
                continue
            
            # 다음 좌표의 값이 현재까지 쌓인 알파벳에 포함되지 않으면
            if graph[nx][ny] not in alpha:
                
                # 문자열 합치기를 그냥 +로 구현
                # 알파벳에 다음 좌표의 알파벳도 넣어줌
                n_alpha = alpha + graph[nx][ny]
                
                # 큐에도 다음 요소로 넣어줌
                q.add((nx, ny, n_alpha))
                
                # 더 큰 값을 answer로 업데이트 시킴
                answer = max(answer, len(n_alpha))

    return answer

print(bfs())

문제 해설

DFS와 BFS의 활용 문제.

처음 문제를 접하고 예시 두개를 맞춰서 자신감을 얻고 간단하게 풀었다고 착각한 문제…

그나마 DFS는 set을 활용하여 문제를 풀었음에도 Pypy3이 아니면 시간 초과가 발생하였고, BFS는 3번째 예시에서 왜 오답인지 너무 뻔해보일 정도로 이유가 명확하여 좌절하였다… ㅠㅠ

결국 구글링을 통하여 다른 분들은 어떤 식으로 BFS를 해결하였나 찾아보니

# set을 활용하여 중복 제거
# 좌표 x, y 와 그 좌표의 알파벳을 set에 넣어줌
q = set([(0, 0, graph[0][0])])

# --- 중략 ---

# 다음 좌표의 값이 현재까지 쌓인 알파벳에 포함되지 않으면
if graph[nx][ny] not in alpha:

    # 문자열 합치기를 그냥 +로 구현
    # 알파벳에 다음 좌표의 알파벳도 넣어줌
    n_alpha = alpha + graph[nx][ny]

    # 큐에도 다음 요소로 넣어줌
    q.add((nx, ny, n_alpha))

    # 더 큰 값을 answer로 업데이트 시킴
    answer = max(answer, len(n_alpha))

위와 같이 탐색하는 알파벳 자체를 별도의 리스트없이 그대로 이어붙이는 형식으로 풀면 중복도 처리할 수 있고, 매번 붙을 때 마다 answer 값도 갱신시켜 주면서 최종적으로 가장 큰 영역의 값을 구할 수 있다는 것을 알게 되었다. 위의 로직을 이해하고 나니 시간 초과도 없이 BFS로 수월하게 풀 수 있었다.

어떤 문제든 기본적인 알고리즘의 활용은 비슷하지만, 그 이상을 생각하는 것은 문제를 많이 접해야만 해결할 수 있는 부분인 것 같다. 생각에 갇혀 있지 않고, 다양한 사고를 할 수 있도록 사고력을 길러야겠다.

댓글남기기

참고