네발로 코딩하는 포메라니안

문제 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 과정 BFS를 떠올리기는 쉬웠는데 K까지 도달하는 개수를 어떻게 셀 지에 대해서 생각하기가 어려웠다. 방문체크를 q에서 꺼낼 때함으로써, 현재 step에서는 중복을 허용하되 다음 step에서는 이전에 방문한 것을 제외하고 방문하도록 할 수 있었다. import java.io.BufferedReader; import java.io.InputStream..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 1. BFS 탐색으로 퍼즐(remove를 쓰기 위해 LinkedList를 사용)과 빈 칸을 각각 분석한다. 1-1. 블럭의 가장 위쪽에서 가장 왼쪽에 있는 블럭을 (0, 0)으로 맞추어 블럭들의 좌표를 변경한다. - setCenter메서드 2. 각 빈칸에 퍼즐을 넣을 수 있는 지 검사한다. 2-1. 개수가 다르면 return false; 2-2. 개수가 같으면 회전시켜가면서 넣을 ..

문제 https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 풀이 과정 특정 노드로 부터 모든 노드의 최단 거리를 저장하기 때문에, BFS 탐색을 했다. 결과 배열에 각 칸을 처음 방문했을 때, (이전 칸의 값 + 1)로 바로 값을 넣는다. 값이 이미 있다면 전에 더 짧은 경로로 왔다는 의미이므로 넘어간다. import java.io.BufferedReader; import java.io.InputStrea..

문제 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 과정 가능한 경로 중 가장 짧은 경로를 찾아야 하므로, BFS로 풀었다. 여기서 해당 경로 과정을 기록할 때는 Queue에 문자열을 넣어도되지만, 문자열을 합치는 비용이 크다. 따라서, 아래와 같이 해당 숫자의 index에 D, S, L, R중 어떤 명령어로 왔는지를 char형으로 저장해놓는다. 결과를 출력할 때는 parent배열을 따라 역으로 올라가면서, 경로를 합쳐준다...

문제 https://www.acmicpc.net/problem/10472 10472번: 십자뒤집기 당신에게 3x3 크기의 보드가 주어진다. 각각의 칸은 처음에 흰색 혹은 검은색이다. 만약 당신이 어떤 칸을 클릭한다면 당신이 클릭한 칸과 그 칸에 인접한 동서남북 네 칸이 (존재한다면) 검은색 www.acmicpc.net 풀이 과정 데이터는 3x3으로 총 9개의 수가 주어지므로, int하나로 비트마스킹을 사용했다. 특정 상태까지의 최단 시간을 구하는 문제이므로 BFS를 사용했고 검은색은 1, 흰색은 0으로 비트마스킹해서 전체 값이 0이면 모두 흰색이므로 종료하도록 했다. import java.io.BufferedReader; import java.io.InputStreamReader; import java...

1. 문제 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 2. 풀이 과정 처음에는 오는 방향에 따라 들어온 방향과 같으면 거울 수를 추가하지 않고, 들어온 방향과 다르면 거울 수를 추가해서 처리했다. PriorityQueue를 사용해서 사용한 거울 수가 작은 경로부터 처리해서 도착지가 나오면 종료했다. 코드는 아래에 [더보기]를 클릭하면 볼 수 있다. 더보기 import java.io.BufferedReader; import java..

1. 문제 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 2. 풀이 과정 특정 상태까지의 최소 이동 시간을 구하기 때문에, BFS로 탐색하였다. 여기서 고민했던 부분은 방문 체크였다. 이미 이전에 고려했던 2차원 배열의 상태는 다시 볼 필요가 없기 때문에, 이 2차원 배열을 int형 숫자하나인 123456780 식으로 변환해서 방문체크를 하고 너비우선탐색을 진행했다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; p..

1. 문제 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 2. 풀이 과정 상근이가 이미 지나간 곳은 불이 번져도 상근이를 따라 잡을 수 없기 때문에, 불이 번지는 건 빈칸만 고려해주었다. 빈칸을 누가 먼저 가냐만 보면 된다. 상근이가 현재 갈 수 있는 위치와 불이 방금 번진 위치를 모두 queue에 넣고, 4방향 탐색으로 갈 수 있는 곳에 표시를 해준다. 이때, 상근이는 불이 다 번지고 난 후에 움직이기 때문에 처음 상근이의 위치는 queue의 마지막에 ..

1. 문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 2. 풀이 과정 보통 DFS, BFS를 같이 쓸 수 있는 문제가 많아서 대부분 DFS로 풀다가 이번에 오랜만에 BFS 방식으로 풀어서 어색했다. 가능한 경로 중에서 최소 길이를 찾는 문제라서 BFS 방식으로 풀어야 한다. 풀이 방식을 간단하게 설명하면, Queue에 방문할 수 있는 층수를 넣고 Queue의 크기만큼 반복문을 돌며 다음 단계에 방문할 수 있는 층을 찾는다. 이미 방문한 층은 다시 방문..

1. 문제 https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 2. 풀이 과정 방법 1. bfs 그래프는 MST로 주어지기 때문에, 인접리스트로 입력을 받았다.구현 방식은 매 query마다 bfs탐색을 하며, 가중치가 k이상인 경우만 더 탐색하도록 한다. 더보기 import java.io.BufferedReader; import java.io.InputStreamReader; import java..