목록BFS (6)

상상쓰

[프로그래머스] 11주차_아이템 줍기

https://programmers.co.kr/learn/courses/30/lessons/87694 코딩테스트 연습 - 11주차 [[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 1) 테두리 좌표 기억하기 2) BFS 알고리즘 사용 으로 접근하였다. 테두리 좌표는 직사각형의 테두리와 내부를 board[][] = 1로 만든 다음, 내부를 board[][] = 0으로 바꿔준다. 어떤 직사각형에서 테두리가 다른 직사각형의 내부라면 board[][] = 0 으로 처..
Coding Test 2021. 10. 20. 13:23
[프로그래머스] 카드 짝 맞추기

https://programmers.co.kr/learn/courses/30/lessons/72415 코딩테스트 연습 - 카드 짝 맞추기 [[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]] 1 0 14 [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]] 0 1 16 programmers.co.kr 너무 힘든 문제였다. 예를 들어 캐릭터가 1, 2, 3이 있다고 하자. 그럼 card = {1 : [1의 좌표], 2 : [2의 좌표], 3 : [3의 좌표]} 1의 좌표가 (0, 0), (3, 2) 라고 한다면, (0, 0) -> (3, 2) 또는 (3, 2) -> (0, 0) 을 생각해줘야 한다. card[i] = list(permutations(card[1])..
Coding Test 2021. 9. 10. 01:29
[프로그래머스] 3주차_퍼즐 조각 채우기

https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 3주차 [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0 programmers.co.kr 위클리 챌린지 3주차 문제이다. 갑자기 난이도가 올라갔다. 문제의 첫 번째 입출력 예로 설명을 하자면, game_board = [1, 1, 0..
Coding Test 2021. 8. 18. 13:39
[프로그래머스] 가장 먼 노드

https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 1부터 시작하여 BFS 알고리즘을 이용하여 구현했다. while 문을 한번 돌 때마다 deque 의 popleft() 함수를 이용하면 1과의 거리가 1씩 늘어나는 번호들의 집합을 얻을 수 있다. from collections import deque, defaultdict def solution(n, edge): answer = 0 dic = defaultdict(list) D = defaultdict(int) D[1] = 1 que..
Coding Test 2021. 7. 16. 17:19
[프로그래머스] 블록 이동하기

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 defaultdict, deque def solution(board)..
Coding Test 2021. 6. 13. 20:19
[프로그래머스] 게임 맵 최단거리

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, 너비 우선 탐색이므로 가장 처음 방문했을 때 계산된 maps[][] 값이 최단 거리가 된다. from collections import deque def solution(maps): answer = -1 n = len(maps) m = len(maps[0]) visit = [[0 for j in ra..
Coding Test 2021. 6. 1. 10:19
Prev 1 Next