https://www.acmicpc.net/problem/9079 9079번: 동전 게임 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 세 줄로 이루어지며, 한 줄에 세 개의 동전모양이 주어지는데, 각각의 동전 표시 사이에는 하나의 공백이 www.acmicpc.net 풀이 모두 같은 면이 보이도록 하는 최소 연산 횟수를 구해야 하기 때문에 BFS를 사용하였다. 또한 이미 탐색했던 상태가 나올 수 있으므로, Map map을 선언하여 (동전상태, 해당 동전상태가 나오기 위한 최소 연산 횟수)를 저장한다. 동전 상태는 다음과 같이 문자열로 저장된다. H T T H T T T H H -> HTTHTTTHH BFS 로직 1. 초기 동전상태를 큐와 Map에 추가한다..

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를 수행하여, 각 지점까지의 최단거리를 구하면 된다. 주어진 지도는 map, 각 지점까지의 최단거리는 answerMap에 저장한다. 원래 갈 수 없는 위치는 0을 출력하고, 원래 갈 수 있는 땅 중에서 도달할 수 없는 위치는 -1을 출력하기 위해, answerMap을 모두 -1로 초기화한다음, map이 0인 위치는 0..

https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net 풀이 BFS를 사용해서 최소 이동 횟수를 구하면 된다. BFS를 수행할 때, checkWall() 메서드를 사용하여 직사각형이 이동할 위치에 벽이 있는지 체크한다. 주의할 점으로는, (1, 1)부터 시작하기 때문에 Sr, Sc, Fr, Fc를 저장할 때 -1을 해야 한다. 코드 import java.io.*; import java.util.*; public class Ma..

https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 풀이 BFS를 사용해서 출발지부터 목적지까지의 최단거리를 구하면 된다. 최단거리를 총 2번 구하는데, 검을 얻지 않는 상태와 검을 얻은 상태의 최단거리를 구하여 비교한다. 둘 중 더 작은 최단거리가 T보다 작거나 같다면 그 값을 출력하고, 그렇지 않다면 Fail을 출력한다. int bfs(int startR, int startC, int destR, int destC): (star..

https://www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 풀이 문제를 이해하기 위해 직접 격자판과 폭탄을 그려보았다. 이 때 폭탄이 설치된 위치에는 폭탄이 설치된 초를 써넣었다. 백준의 예시를 봐도 확인할 수 있다. 이를 보면 2초 후 부터는 폭탄 채우기와 폭탄 터뜨리기가 번갈아 수행되는 것을 알 수 있었다. 따라서 int형 2차원 배열을 선언하여 빈 칸은 -1, 폭탄이 있으면 해당 폭탄이 설치된 초를 저장하도록 하여 로직을 수행하도록 했다. 로직 1. 먼저 격자 상태를..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 풀이 BFS를 응용하여, 첫째 줄의 숫자를 고르면 그 숫자에 둘째 줄에 있는 숫자를 큐에 집어넣는 과정을 반복해서 최종적으로 각 숫자들이 2번씩 포함되는지를 체크하였다. 한 사이클을 찾아내면, 첫째 줄과 둘째 줄이 같은 숫자들을 추가하여 크기를 구하여 최대 크기의 사이클을 계속해서 업데이트하는 로직을 생각했다. 하지만 사이클이 여러 개 있을 수 있고, 각 숫자는 오직 1개 이하의 사이..

https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 풀이 먼저 배열 값을 입력받을 때 치즈의 개수를 카운트해서 cheese에 저장한다. 그 다음 while문을 사용하여 cheese가 0이 될 때까지 BFS를 수행한다. BFS는 배열의 처음 위치를 시작점으로 삼는다. 0인 경우에는 위치를 큐에 넣어 탐색을 계속하도록 하고, 1인 경우에는 해당 칸 값을 0으로 변경하고 cheese--를 한다. 코드 import java.io.*; import java.util..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 N*N 크기의 배열을 탐색하여 국경선이 열려 연결되는 국가를 찾아내고, 그 국가의 인구 수를 변경해야 한다. 먼저 2중 for문으로 N*N 크기의 배열을 탐색하고, 각 위치마다 BFS를 통해 연결되는 위치들을 찾아내서 인구 수의 총합을 찾아내고 변경해야 한다. main() 함수의 로직 1. N, L, R을 입력받고 N*N 크기의 배열을 할당하고 값을 입력받는다. 2. while..

https://www.acmicpc.net/problem/1325 A 방향으로 연결되는 간선을 추가해야 한다. 코드 (시간초과) import java.io.*; import java.util.*; public class Main { static ArrayList answer = new ArrayList(); static ArrayList graph = new ArrayList(); static int max = 0; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new Stri..

https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 인접리스트로 그래프를 생성한 후, 완전탐색을 사용하여, 각 전선이 끊어진 경우의 두 전력망의 송전탑 개수의 차이를 구한다. 하나의 전력망의 송전탑 개수는 BFS를 사용하여 구한다. 코드 import java.util.*; class Solution { public int solution(int n, int[][] wires) { // 인접리스트로 그래프 생성 LinkedList[] graph..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구해야 한다. 즉, 최댓값을 구해야 하므로 벽 3개를 세울 수 있는 모든 경우의 수를 구해 그 중 안전 영역 크기의 최댓값을 구해야 한다. 문제를 풀기위해 전체 로직을 3단계로 나누었다. 1. 빈 칸 중 3개 선택(DFS/완전탐색) 2. 바이러스 전파(BFS or DFS) 3. 안전영역 크기 세기(이중 for문) 먼저 main 함수에서..

11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 트리라고 해서 트리 구조를 만들어야 하나? 라고 생각할 수도 있는데, 그래프를 그려서 해결할 수 있다. 인접 리스트로 그래프의 정보를 저장하고, 루트 노드에서부터 DFS또는 BFS로 탐색을 시작하여 아직 방문하지 않은 노드를 찾을 때마다 부모 노드 저장 배열(parent)에 부모 노드 번호를 저장하면 된다. 코드 import java.io.*; import java.util.*; public class Main { static int[] parent; //부모 노드 저장 배열 public static void main(S..