[BOJ] 1987번: 알파벳

 

 

문제 링크

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

 

 

TIL

• dfs와 공통점
  • visited check
• dfs와 차이점
  • 백트래킹은 차단 조건 존재 > 더 이상 방문 안함
  • 알파벳 문제에서 visited check는 동일하지만, alphabet check를 한다는 점에서 차단 조건이 추가됨
• 최대로 갈 수 있는 길을 구하는 것이기 때문에 base condition이 없어도 되긴 함 (return 조건)
  • 그럼 더이상 진행될 수 없을 때까지 방문하게 됨 !!
• visited_alpha.remove(grid[ny][nx])를 하면 안된다고 생각했는데 틀림
  • set() 구조이기 때문에 2번 방문한건데 backtrack에서 삭제하면 오류 발생한다고 생각
  • 결론적으로, 한 번만 방문할 수 있기 때문에 2번 방문한다는 가정부터 틀림!! 따라서 remove 그냥 해도 됨
• max_len으로 처리해줘야 하는 이유: 한붓그리기
  • max_len안하고 방문할때마다 더하면 한붓그리기가 아니라 뭉텅이 모두 포함됨
  • cnt += 하는 경우
    >>" 독립적인 섬의 개수와 각 섬의 크기를 구하라"에서는 가능 (한붓그리기와 같은 경로가 아닌 "크기"만을 묻는 문제)
  • max_len 하는 경우
    >> 처음부터 시작해서 도달할 수 있는 최대 길이를 구하라 (한붓그리기 해야함, "크기"만이 아니라 "크기+경로"를 묻는 문제)

< 수정 중이었던 원래 코드 >

import collections

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

grid = []
for i in range(r):
    grid.append(list(input()))

def is_valid(cy, cx):
    if 0<=cy<r and 0<=cx<c and visited_alpha[grid[cy][cx]] <= 0:
        return True
    return False

visited_coord = [[False for _ in range(c)] for _ in range(r)]
visited_alpha = collections.defaultdict(int)

directions = [(0,1), (1,0), (-1,0), (0,-1)]

def isolated(coord):
    cy, cx = coord[0], coord[1]
    for dy, dx in directions:
        ny, nx = cy+dy, cx+dx
        if is_valid(ny,nx) and visited_coord[ny][nx]==0:
            return False
    return True

def backtrack(coord, ans):
    if used_alpha == 0:
        return ans

    cy, cx = coord[0], coord[1]
    for dy, dx in directions:
        ny, nx = cy+dy, cx+dx
        if is_valid(ny,nx) and visited_coord[ny][nx]==0:
            ans.append((ny,nx))
            visited_coord[ny][nx] = 1
            if visited_alpha[grid[ny][nx]] == 0:
                visited_alpha[grid[ny][nx]] = 1
            else: visited_alpha[grid[ny][nx]] += 1
            print(visited_alpha)
            res = backtrack((ny,nx), ans)
            if res:
                return ans
            ans.pop()
            visited_alpha[grid[ny][nx]] -= 1

ans = [(0,0)]
visited_alpha[grid[0][0]] = 1
print(len(backtrack((0,0), ans)))

 

 

Code

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

grid = []
for i in range(r):
    grid.append(list(input()))

def is_valid(cy, cx):
    if 0<=cy<r and 0<=cx<c and grid[cy][cx] not in visited_alpha:
        return True
    return False

visited_coord = [[False for _ in range(c)] for _ in range(r)]
visited_alpha = set()

directions = [(0,1), (1,0), (-1,0), (0,-1)]

def dfs(coord, cnt):
    has_moves = False
    max_cnt = cnt
    cy, cx = coord[0], coord[1]
    for dy, dx in directions:
        ny, nx = cy+dy, cx+dx
        if is_valid(ny,nx) and visited_coord[ny][nx]==0:
            has_moves = True
            visited_coord[ny][nx] = 1
            visited_alpha.add(grid[ny][nx])
            max_cnt = max(max_cnt, dfs((ny,nx), cnt+1))
            visited_coord[ny][nx] = 0
            visited_alpha.remove(grid[ny][nx])
    if not has_moves:
        return cnt
    
    return max_cnt

visited_alpha.add(grid[0][0])
visited_coord[0][0]=1
print(dfs((0,0), 1))

• 처음에는 visited_coord[ny][nx] = 0 으로 다시 backtrack을 안했는데, 그 이유는 한 번 방문했지만 가능성이 없는 곳은 다시 방문하면 안되니까 visited는 냅두고 alpha만 remove했음
• 이렇게 생각하면 안되는 이유: 어차피 for문으로 돌기 때문에 해당 방향으로는 1번만 감 (하나의 가능성)
  • 예를 들어, 123 순서로 해서 가능성이 배제됐을 때, 1->2->3 으로는 3을 방문하면 안되지만 1->2->4->5->3 는 다른 가능성이니까 방문 가능해야함. 
  • 즉, 해당 노드가 다른 길을 돌아서 또 방문될 수 있어야함
• visited_coord[ny][nx] = 0  필수 !!!!
• 이 코드는 시간 초과 뜸 ㅠㅠ (코드 자체는 맞는듯)

[최종 코드]

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

grid = []
for i in range(r):
    grid.append(list(sys.stdin.readline().strip()))   #list(input()))

visited_coord = set()
directions = [(0,1), (1,0), (-1,0), (0,-1)]

# 한붓그리기
def dfs(coord, cnt):
    has_moves = False
    max_cnt = cnt
    cy, cx = coord[0], coord[1]
    for dy, dx in directions:
        ny, nx = cy+dy, cx+dx
        if 0<=ny<r and 0<=nx<c and (ord(grid[ny][nx])-65) not in visited_coord:
            has_moves = True
            visited_coord.add(ord(grid[ny][nx])-65)
            max_cnt = max(max_cnt, dfs((ny,nx), cnt+1))
            visited_coord.remove(ord(grid[ny][nx])-65)
    if not has_moves:
        return cnt
    
    return max_cnt

visited_coord.add(ord(grid[0][0])-65)
print(dfs((0,0), 1))

• 생각해보니까 알파벳 중복이 되면 어차피 못가기 때문에, 알파벳으로만 visited check를 해도 됨 !!!!! >> 시간 줄일 수 있음
• 문자(char)를 그냥 비교 처리하는 것보다 ord를 사용하여 유니코드로 정수화하면 비교 속도 훨씬 빨라짐 !! >> 시간 초과 해결
• python3로는 시간초과가 나지만, pypy3로 제출 성공함
• 이 코드에서 has_moves는 필수적인가? >> 확인 필요
• python3 시간초과 나지 않으려면 bfs 사용해야 함