본문 바로가기

알고리즘

 (305)
[프로그래머스] 퍼즐조각 채우기 🤔 문제분석 게임테이블에서의 빈칸의 퍼즐과 맞춰야할 테이블에서의 퍼즐을 구한뒤에 퍼즐을 돌려가면서 빈칸에 맞추어본다. 맞추는 로직은 equals를 활용하였는데 퍼즐의 높이와, 너비, 그리고 값 까지 모두 같을경우에만 퍼즐을 조립해준다. BFS로 방문한 그룹을 배열로 퍼즐로 변환하는 구현과 배열을 돌리는 구현이 이 문제의 핵심이라고 생각한다. 💻 코드 import java.util.*; class Solution { boolean[][] visited; boolean[][] visited2; int[][] game_board; int[][] table; int h, w; int answer = 0; public int solution(int[][] game_board, int[][] table) { thi..
[백준] 9370번 : 미확인 도착지 9370번: 미확인 도착지 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 🤔 문제분석 s에서 e로 갈때 g, h를 방문했는지 여부를 확인하는 문제로 데이크스트라를 s에서 시작, g에서 시작, h에서 시작하여 각각의 거리를 측정한뒤 아래의 조건을 만족하면 s 에서 e로 갈때 g, h를 방문했는지 확인 할 수 있다. d_s[g] + d_g[h] + d_h[e] == d_s[e] 일때 d_s[h] + d_h[g] + d_g[e] == d_s[e] 일때 💻 코드 import sys import heapq in..
[백준] 14442번 : 벽 부수고 이동하기 2 14442번: 벽 부수고 이동하기 2 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 🤔 문제분석 너비우선탐색으로 해결 할 수 있는데 벽을 부순 횟수를 방문배열에 따로 추가하여 해결하였습니다. 벽을 부수고 먼저 이동한 것들이 끝까지 도달하지 못하고 미리 방문배열을 초기화 하였다면 벽을 부수지 않고 온 것이 끝까지 도달하지 못하는 상황이 발생하여 벽을 부순 횟수를 3차원에 추가를하여 벽을 부순횟수도 체크를 해주어야한다. 💻 코드 import sys from collections..
[백준] 14938번 : 서강 그라운드 14938번: 서강그라운드 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 🤔 문제분석 플로이드 워셜, 데이크스트라를 떠올리면 된다. 플로이드워셜 플로이드 워셜로 모든 노드까지의 모든 최단경로를 구한뒤, i번노드에서 다른노드까지 거리가 m이하인 경우만 아이템을 획득하게 만들면 된다. 데이크스트라 i번 노드에서 다른노드까지의 최단 거리를 구한뒤 ( 데이크스트라 ) 모든 거리가 m 이하인 경우만 아이템을 획득 할 수 있으므로 m이하인 거리만 item을 획득하게 하면된다. 💻 코드 플로이드워셜 import sys inpu..
[백준] 2668번 : 숫자고르기 2668번: 숫자고르기 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 🤔 문제분석 깊이 우선탐색으로 아래 숫자를 뽑아서 그 숫자로 이동하면서, 위쪽 집합과 아래쪽 집합이 동일할 경우 정답 리스트에 값을 추가시켜줍니다. 위쪽 집합과 아래쪽 집합이 같다는건 결국 집합을 만들 수 있다는 조건을 만족시키기 때문입니다. 💻 코드 import sys input = sys.stdin.readline N = int(input()) nums = [int(input()) for _ in range(N)] def ..
[백준] 5427번 : 불 5427번: 불 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 🤔 문제분석 너비우선탐색을 이해하면 쉽게 풀 수 있는데, 불을 먼저 방문한뒤 승범이를 방문하면 불이 먼저 번지게되고 번지지 않은 위치를 승범이가 탐색 할 수 있으니 문제에서 요구하는 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동 할 수 없는 조건을 잘 만족 시킬 수 있습니다. 💻 코드 import sys from collections import deque input = sys.stdin.readline moves = [(0, 1), (0, -1), ..
[백준] 1774번 : 우주신과의 교감 1774번: 우주신과의 교감 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 🤔 문제분석 우주신끼르는 가장 짧은 길이로 연결되어야한다. 최소신장 트리를 이용하여 문제를 해결하면된다. 최소 신장 트리는 가장 짧은 간선을 사이클이 존재하지 않을때까지 반복하여 유니온한다. 💻 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) node = [] for _ in range(N): X, Y = map(int, i..
[백준] 1956 : 운동 1956번: 운동 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 🤔 문제분석 사이클이 존재하면서 두 마을 사이의 거리중에서 가장 짧은 거리를 구하는 문제로 플로이드 워셜을 이용하여 문제를 해결한다. 플로이드 워셜은 i번째 마을에서 j번째 마을까지 최단경로를 구한다. 모든 i와 j에 대해서 (i번째 마을에서 j번째 마을까지 + j번째 마을에서 i번째 마을까지) 를 구하게 되면 가장 짧은 사이클을 구할 수 있다. 만약 i와 j가 연결되어있지 않다면 INF로 둔다. 💻 코드 im..

티스토리툴바