[프로그래머스] 양과 늑대(Python)
https://programmers.co.kr/learn/courses/30/lessons/92343 코딩테스트 연습 - 양과 늑대 [0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5 programmers.co.kr 쉽지 않았던 문제다. 풀면서 생겼던 문제는 현재 상태에서 갈 수 있는 노드를 찾는 과정에서 객체를 같이 참조하면서 무한루프를 돌았다. 그 부분을 어떻게 할지 고민했다. 알고리즘은 다음과 같다. 1. 루트 노드부터 ..
2022. 1. 28.
[프로그래머스] 블록 이동하기 (Python)
https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 힘든 구현 문제다. 이게 맞나 싶으면서 그냥 구현했다. bfs로 풀었다. 나의 풀이 from collections import deque,defaultdict def solution(board): length = len(board) visited = defaultdict(int) visited[(0,0,0,1)] = 1 q = deque([(0,0,0,1,0)]) while q: x, y, ..
2021. 11. 18.
[프로그래머스] 아이템 줍기 (Python)
https://programmers.co.kr/learn/courses/30/lessons/87694 코딩테스트 연습 - 아이템 줍기 [[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]] 1 3 7 8 17 [[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]] 9 7 6 1 11 [[2,2,5,5],[1,3,6,4],[3,1,4,6]] 1 4 6 3 10 programmers.co.kr 어려웠던 문제다. bfs로 풀었다. 1. 시작 지점에서부터 U, D, R, L 방향으로 하나씩 이동 2. 이동 후 조건에 맞는지 확인 - 좌표 범위를 넘어갔으면 continue - 방문 한 적이 있다면 continue - 주어진 직사각형들을 하나씩 순회하며 직사각형 좌표를 받는다..
2021. 11. 11.
[프로그래머스] 경주로 건설 (Python)
https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 어려웠다... bfs + dp로 풀어냈는데 계속 틀려서 확인해보니 board = [ [..
2021. 11. 10.
[프로그래머스] 전력망을 둘로 나누기 (Python)
https://programmers.co.kr/learn/courses/30/lessons/86971 코딩테스트 연습 - 전력망을 둘로 나누기 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr 전선을 하나씩 끊어 보며 bfs로 풀었다. from collections import deque def solution(n,wires): answer = 101 for i in range(len(wires)): wire = wires[:i] + wires[i+1:] graph = [[] for _ in range(n+1)] visited = [False for _..
2021. 11. 3.
[프로그래머스] 게임 맵 최단거리(Python)
https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 전형적인 BFS 문제다 나의 풀이 from collections import deque def solution(maps): n,m = len(maps), len(maps[0]) visited = [[0]*m for _ in range(n)] visited[0][0]=True move = [(1,0),(-1,0..
2021. 10. 31.
