[프로그래머스] 양과 늑대
특정 노드에서, 다른 노드로 어떻게 이동하지?? 가 제일 큰 고민거리였습니다. 예를 들어 0->1을 간 상황이라면, 다음에 이동할 수 있는 노드가 2, 4, 8인데 2, 4는 자식 노드들이고, 8은 거슬러 올라가야 하는데 어떻게 가지? 라는 생각을 했습니다. 그런데, 갈 수 있는 노드들의 공통점은 "해당 노드의 부모 노드는 방문했고, 해당 노드는 방문하지 않은 상태"일 때 갈 수 있었습니다. (풀이 2번) 또는, 0번 노드에 있을 때 다음으로 갈 수 있는 노드들은 0번 노드의 자식들인 1, 8이고 1로 이동했을 때 갈 수 있는 노드들은 기존 갈 수 있던 1,8에서 1(지금 도착한 노드)를 제외한 8번 노드 + 1번 노드의 자식들인 2, 4번 노드입니다. (풀이 1번) 풀이1 import sys sys.s..
[프로그래머스] 미로 탈출 명령어
import sys sys.setrecursionlimit(10**6) def solution(n, m, x, y, r, c, k): dx = [1, 0, 0, -1] #남서동북 dy = [0, -1, 1, 0] info = { 0 : 'd', 1 : 'l', 2 : 'r', 3 : 'u' } res = "impossible" flag = False visited = [] def dfs(i, j, cnt): nonlocal res, flag, visited if flag : return #k안으로 어차피 못갈 바에 return if abs(r-i)+abs(c-j)+cnt > k: return #도착했으면 flag로 막아주기 if cnt == k and i == r and j == c: res = ''.j..
[프로그래머스] 멀리 뛰기 파이썬
문제 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다. 풀이 딱 봐도 익숙한 유형입니다. 예전에 수학 문제 풀 때 많이 나왔던... 그런데 머리로는 생각이 잘 되는데 코드를 구현하자니 어렵습니다. 결국 이 문제도 dp문제입니..
