BFS19 (java)프로그래머스 미로 탈출 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제를 보자 마자 bfs라는 풀이법을 떠올렸다. 먼저 레버에 도착하는 최소의 거리를 구하고 또 레버에서 bfs를 시작해서 출구로 가는 최소한의 거리를 구하면 된다. 그런데 레버에 도착하지 못하는 경우에는 바로 return -1을 해주어야 하는데 이 경우를 찾지 못해서 조금 해맸다. import java.util.*; class Solution { public int solution(String[] maps) { int N = maps.length; int M = maps[0].length(); ch.. 2023. 7. 20. (java) BOJ G4 4179 불! 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 문제풀이 그래프 탐색을 하면 된다. 주의할 점: 지훈이가 밖으로 나가야 한다. 그리고 불퍼지는 것을 외부에 queue로 따로 빼주어서 가장자리 불만 퍼지게 해주어야 시간 초과에 걸리지 않는다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queu.. 2023. 7. 13. 5427번 불(python3) https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 딱 봐도 bfs로 접근하면 풀리는 문제다. 이 문제의 포인트는 bfs를 진행할 때 불이 번지는 것부터 하는 것이다. 그리고 사람이 방문했던 칸은 불이 번질 필요가 없다. 어차피 사람보다 늦게 불이 도착하면 그 불은 이 문제에는 상관이 없어지기 때문이다. import sys from collections import deque dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] def bfs().. 2022. 2. 21. 11559번 Puyo Puyo(python3) https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 뿌요뿌요 게임을 구현해 보는 문제다. bfs로 4개 이상 연결된 블록들을 찾아내서 ' . '으로 바꿔주고 ' . '으로 바뀐 부분을 채워주면 된다. import sys from collections import deque data = [] for _ in range(12): temp = input() temp2 = [] for i in temp: temp2.append(i.. 2022. 2. 18. 14888번 연산자 끼워넣기(python3) https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net bfs로 이 문제를 접근하였다. 지도(상하좌우 이동)문제에서는 bfs 적용을 제대로 마스터했다고 생각했는데 이와 같은 문제에서는 제대로 적용하지 못한다는 것을 알게 되었다. 각 bfs마다 따로 남은 연산자의 갯수 deepcopy를 통해서 할당해주면 된다. 그리고 count가 숫자의 갯수보다 하나 작을때까지 bfs를 적용해주면 된다. from .. 2022. 2. 11. 2573번 빙산(python3) https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net bfs를 적용하면 된다. 이 문제의 핵심은 빙산을 깎을 때, 그 깎인 높이가 다른 빙산을 깎을 때 영향을 주면 안된다는 것이다. 나는 처음에 코드를 작성했을 때 배열의 깊은복사를 사용해서 작성했기 때문에 깊은 복사를 사용하지 않고 구현하는 방법을 찾아보았다. from collections import deque import copy N, M = map(int, input().split()) .. 2022. 2. 6. 이전 1 2 3 4 다음