본문 바로가기

BFS16

[프로그래머스 Lv3] : 블록 이동하기 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/60063 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 로봇이 지도의 가장 끝점인 (N, N)까지 이동하는 데 필요한 최소 시간을 리턴해주자. 풀이 무지의 로봇은 2칸을 차지하는 로봇이다. 상,하,좌,우로 이동하거나 90도 회전이 가능하다. 문제를 제대로 안 읽고 놓여져있는 방향으로만 이동이 가능한 줄 알고 문제를 풀어서 시간을 낭비했다.. 탐색 방법은 BFS를 이용하고, 방문체크가 중요하다. 로봇이 두 칸을 차지하기 때문에 1차원 배열로 .. 2022. 7. 25.

[프로그래머스 Lv3] : 카드 짝 맞추기 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/72415 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 카드 뒤집기 게임에서 모든 카드의 짝을 맞추는 데 필요한 최소 커서 이동 횟수를 리턴하자. 풀이 어디에 어떤 카드가 있는 지는 이미 알고 있지만, 어떤 카드부터 뒤집어야 가장 적은 횟수로 모든 카드의 짝을 맞출 수 있는 지는 알 수 없다. 그렇기 때문에 모든 경우의 수를 다 해보고 최소 횟수를 구해준다. 보드가 4 X 4 크기로 그리 크지 않기 때문에 모든 경우를 다 해봐도 시간초과가 .. 2022. 7. 25.

[프로그래머스 Lv3] : 경주로 건설 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 죠르디가 경주로를 건설하는 데 필요한 최소 비용을 계산할 수 있도록 도와주자. 풀이 인접한 상하좌우로 움질일 수 있으며 직선 도로를 건설하는 데는 100원, 코너를 건설하는 데는 500원이 소요된다. 즉, 같은 방향으로 이동할 때는 도로만 건설하면 되니까 100원 다른 방향으로 이동할 때는 도로 + 코너를 건설해야하므로 600원의 비용이 발생한다. "방향"이 중요한 요소임을 알 수 있다.. 2022. 7. 14.

[프로그래머스 Lv4] : 지형 이동 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/62050 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 모든 칸에 방문하기 위한 사다리 설치 비용의 최솟값을 리턴해주자. 풀이 모든 칸에서 상하좌우로 이동할 수 있으며 높이 차가 주어진 height 값보다 작거나 같으면 그냥 이동할 수 있지만 높이 차가 height 보다 크다면 높이 차이만큼의 비용을 내고 사다리를 설치해야한다. 각 칸을 정점으로 봤을 때, 모든 정점을 이어지도록 하는 길을 찾아야한다는 뜻이다. 임의의 칸을 기준으로 상하좌우.. 2022. 7. 11.

[BOJ] 23289 : 온풍기 안녕! 문제 링크 23289번: 온풍기 안녕! (acmicpc.net) 23289번: 온풍기 안녕! 유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기 www.acmicpc.net 온풍기를 이용해서 조사하는 칸의 온도가 모두 특정 온도 이상이 되도록 하는데 테스트 과정을 몇 번 거쳐야하는지 계산하는 구현 문제. 여기서는 테스트 과정 한 번을 초콜릿을 하나 먹는 것으로 표현했다. 풀이 R x C 크기의 격자에 온풍기가 놓여있다. 이 온풍기에서 바람이 한 번 나오면 문제에서 제시된 그림대로 격자 칸의 온도가 상승하게 된다. 성능 테스트의 과정은 다음과 같다. 1. 집에 있는 모든 .. 2022. 6. 9.

[BOJ] 23288 : 주사위 굴리기 문제 링크 23288번: 주사위 굴리기 2 (acmicpc.net) 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 지도위에 놓인 주사위를 굴리며 점수를 획득하는 게임. 풀이 N x M 크기의 지도에 (1,1) 좌표에 주사위가 놓여져있다. 2 4 1 3 5 6 주사위의 초기 상태 전개도는 위와 같다. 윗면이 1이고, 아랫면이 6 오른쪽면이 3이다. 1. 주사위가 이동 방향으로 한 칸 굴러간다. 만약, 이동 방향에 칸이 없다면, 이동 방향을 반대로 한 다음 한 칸 굴러간다. 2. 주사위가 도착한.. 2022. 6. 3.

[BOJ] 21609 : 상어 중학교 문제 링크 21609번: 상어 중학교 (acmicpc.net) 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 상어 초등학교에 이어서 상어 중학교 문제. 역시 구현문제다. 풀이 N x N으로 주어진 격자를 주어진 과정에 따라 블록그룹을 삭제하는 게임. 최종 점수를 출력하자. 블록 그룹에는 반드시 같은 색깔의 블록들이 포함되어야하며, 무지개 블록은 어느 그룹에나 포함될 수 있다. 그리고 검은색 블록은 어떤 그룹에도 들어갈 수 없다. 이때 블록그룹에 일반 블록이 1개 이상 들어가야하며 그룹의 크기는 2 이상이어.. 2022. 6. 2.

[BOJ] 19238 : 스타트 택시 문제 링크 19238번: 스타트 택시 (acmicpc.net) 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 모든 손님을 최단거리로 태우고 싶어하는 백준이를 도와주자. 풀이 백준이가 운전하는 택시는 현재 위치에서 가장 가까운 손님을 태우고, 그 손님을 목적지로 데려다준다. 만약 연료가 부족해서 손님을 태우지 못하거나, 손님을 태우고 목적지까지 가지 못한다면 -1을 출력하고 종료한다. 연료가 충분해서 손님을 태워서 목적지에 데려다 줄 수 있다면, 손님의 위치에서 목적지까지.. 2022. 5. 23.

[BOJ] 17142 : 연구소 3 문제 링크 17142번: 연구소 3 (acmicpc.net) 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 연구소 모든 칸에 바이러스를 퍼트리는데 걸리는 시간을 구하는 BFS 문제. 풀이 연구실을 N X N 크기의 칸으로 표현했을 때 각 칸은 0 빈 칸, 1 벽, 2 바이러스 중에 하나로 채워진다. 바이러스에는 활성 바이러스와 비활성 바이러스가 있다. 둘다 바이러스지만 활성 바이러스는 전염성을 가지고 비활성 바이러스는 전염성이 없다. 하지만 활성 바이러스가 비활성 바이러스와 만나면 활성화시킬 수 있다. 2 ~ 10개 .. 2022. 5. 17.

이전 1 2 다음

티스토리툴바