https://www.acmicpc.net/problem/2206풀이BFS를 사용하여 최단 경로를 구하는 문제다. 이동하는 도중에 최대 1개까지 벽을 부수고 이동할 수 있기 때문에, 처음 풀 때는 모든 벽에 대해서 1개씩 부서졌을 때 BFS를 수행했다. 하지만 시간초과가 났다. 다른 사람의 풀이를 찾아본 결과 visited 배열을 3차원으로 선언하여 벽을 부쉈을 때와 부수지 않았을 때를 따로 처리하였다.boolean[][][] visited = new boolean[n][m][2]; // [r][c][0] = 벽을 부수지 않고 이동한 경우 , [r][c][1] = 벽을 부수고 이동한 경우 BFS 수행 과정1. (0, 0) 좌표에서 시작한다. 시작하는 칸도 포함해서 카운트하기 때문에 dist는 1, des..

https://www.acmicpc.net/problem/7576풀이대표적인 BFS 문제다.토마토 상태를 입력받을 때 익지 않은 토마토의 개수를 미리 카운트하고, BFS를 하며 익은 토마토의 개수를 카운트한다.BFS가 종료된 후 익지 않은 토마토가 있다면 -1을 출력하고, 모두 익었다면 모두 익을 때까지의 걸린 시간을 출력한다.코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static int n, m; static int[][] map; static int[] dr = {0, 1, 0, -1}; s..

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..