[백준/Python] 병든 나이트 1783

1. 첫 번째 풀이(fail): 백트래킹

'''
이건 백트래킹으로 풀면 될 듯!
더 이상 움직일 있는 칸이 없다면 끝인걸로
'''
def move(i,cr,cc):
    if i == 0:
        nr,nc = cr-2, cc+1
    elif i == 1:
        nr,nc = cr-1, cc+2
    elif i == 2:
        nr,nc = cr+1, cc+2
    else:
        nr,nc = cr+2, cc+1
    return nr,nc

def dfs(cr,cc,cnt,visited,used):
    global maxCnt
    # 탐색
    for i in range(4):
        nr,nc = move(i,cr,cc)
        if not(0<=nr<r and 0<=nc<c) or visited[nr][nc]:
            continue
        visited[nr][nc] = True
        used[i] +=1
        dfs(nr,nc,cnt+1,visited,used)
        visited[nr][nc] = False
        used[i] -=1
    # 더 이상 움직일 곳이 없다면 최댓값 갱신 후 return
    if cnt > 4:
        for isUsed in used:
            if not isUsed:
                return
    maxCnt = max(maxCnt, cnt)
    return

def main():
    global r,c,maxCnt,visited
    r,c = map(int,input().split())
    maxCnt = 0
    visited = [[False]*c for _ in range(r)]
    used = [0]*4
    # 가장 왼쪽 아래에서 출발
    dfs(r-1,0,1,visited,used)
    return maxCnt

print(main())

 

 

2. 두 번째 풀이(success): 그리디

'''
이건 백트래킹으로 풀면 될 듯!
    -> n,m 범위가 너무 커서 안됨

그리디
    -> 2칸위로+2칸아래로 or 1칸위로+1칸아래로 조합중 무조건 하나 택1
    -> 이동 횟수가 4번보다 적은 경우 이동 방법에 제약이 없다 == 이동 횟수가 4번이상이라면, 모든 방법을 한번씩 다 사용한 후에야 중복해서 사용할 수 있다
'''
def main():
    r,c = map(int,input().split())
    # 2칸위로+2칸아래로 조합으로 갈 수 있는 경우 -> 1칸위로+1칸아래로 한번 하고, 이후에 2칸위로+2칸아래로 반복, c<=5라면 그대로 c-1 return
    if r>=3:
        if c<=4: return c
        elif c<=6: return 4
        else: return 3+(c-5)
    # 이 경우 2칸위로+2칸아래로 쓸 수가 없음 -> 한칸위로+한칸아래로 경우만 생각해주자
    elif r==2:
        if c<3: return 1
        elif c<7: return c//2 +1 if c%2 else c//2
        else: return 4
    # 위,아래로 이동 불가
    else:
        return 1

print(main())