jae_coding

문제 https://www.acmicpc.net/problem/16173 16173번: 점프왕 쩰리 (Small) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 구현 시작점: 왼쪽 맨위, 종료점: 오른쪽 맨 아래 구간: N x N matrix (2

문제 문제 링크 문제 접근 N x N의 바둑판 흰방(1): 통과가 가능하다 검은방(0): 통과가 불가능하다 (1,1)에서 (8,8)을 가기 위해서 검은방을 흰방으로 최소한으로 바꿔서 통과하라 상하좌우에 visited를 이용하여 탐색을 하지 않은 곳은 인접 이전 visited값이나 visited +1값으로 변경 만약 흰방(1)일 경우에는 q.appendleft를 이용하여 우선 탐색(popleft를 사용하기 때문)하고 이전 visited값과 동일하게 해준다. 하지만 검은 방(0)일 경우에는 q.append를 이용하여 후순위로 미룬다. 그리고 visited + 1을 해준다. (찾는 것이 검은방을 흰방으로 변경하는 개수를 최소화한 것을 출력하라고 했기 때문이다) 코드 import sys from collecti..

문제 문제 링크 문제 접근 BFS N x M 크기의 보드와 4개의 버튼으로 이루어진 게임 버튼은 상하좌우 4가지가 있다. 버튼을 누르면 두 동전이 버튼에 쓰여있는 방향으로 동시에 이동한다. 1. 벽이면 동전은 이동하지 않는다 2. 이동하려는 칸에 칸이 없으면 동전은 떨어진다 3. 그 외의 경우에는 원하는 방향으로 이동한다. 두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇번 눌러야 할까? o: 동전 .: 빈 칸 #: 벽 동전의 개수는 항상 2개 10번 이상의 버튼클릭을 할 경우 -1출력 코드 import sys from collections import deque def BFS(board, coins_location): d = [(-1, 0), (0, -1), (1, 0), (0, 1)] co..

문제 문제 링크 문제 접근 사탕의 종류: C(빨간색), P(파란색), Z(초록색), Y(노란색) N x N 행렬에 사탕을 채워넣는다. 사탕의 색이 다른 인접한 두칸을 고른다. 고른 칸에 들어있는 사탕을 서로 교환한다. 가장 긴 연속적인 부분 행 또는 열을 고른 후 사탕의 최대 개수를 출력한다. 코드 import sys def board_max_value(board, N): row_count, col_count = 1, 1 # 행 개수 확인 for i in range(N): temp = 1 for j in range(1, N): if board[i][j-1] == board[i][j]: temp += 1 else: row_count = max(row_count, temp) temp = 1 row_count..

문제 문제 링크 문제 접근 DFS - 모든 노드를 방문하고 싶을 때 사용한다. - Root node를 시작으로 다음 분기까지 넘어가기 전에 완전히 탐색하는 것!! - 한 방향으로 계속 탐색을 하다가 더 이상 탐색할 수 없을 때, 갈림길로 돌아와 완전히 탐색한다. - 어떤 노드를 방문했었는지 여부를 반드시 확인해야한다. BFS - Root node를 시작해서 인접한 노드를 먼저 탐색하는 방법 - 시작점에서 가장 가까운 점을 먼저 방문한다 -> 최단 경로나 임의의 경로를 찾고 싶을 때 사용한다 - 재귀적으로 동작하지 않으며, queue를 이용하여 반복적 형태로 구현한다. 코드 import sys from collections import deque # N: 정점의 개수, M: 간선의 개수, V: 탐색을 시작..