본문 바로가기

BFS

[백준 2206] 벽 부수고 이동하기(JAVA)

CodingTEST 2024. 2. 22. [백준 2206] 벽 부수고 이동하기(JAVA) 백준 2206번 문제 - 벽 부수고 이동하기 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 분석 [0,0] 부터 [N,M] 까지 이동해야한다. 이동할 때, 최단 거리를 구하여라. 0은 이동 가능 1은 벽, 이동 불가능 이동 중 한 번만 벽을 뚫을 수 있다. [0,0] 부터 [N,M] 까지 이동하지 못할 경우 -1을 반환한다. 해결 포인트 BFS 사용 벽을 뚫고 방문한 경우와 벽을 뚫지 않고 방문한 경우는 다른 방문 처리를 해야한다. visited배열을 3차원 배열로 구현 boo..

[백준 11404] 플로이드(JAVA)

CodingTEST 2024. 2. 11. [백준 11404] 플로이드(JAVA) 백준 11404번 문제 - 플로이드 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 분석 n(2 ≤ n ≤ 100)개의 도시가 있다. 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성 해결 포인트 플로이드–워셜 알고리즘 이용 (사실 BFS로 풀었지만 설명 읽어보니 이게 플로이드–워셜 같음) 방문처리를 위한..

[백준 16953] A → B (JAVA)

CodingTEST 2024. 1. 14. [백준 16953] A → B (JAVA) 백준 16953번 문제 - A → B 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제 분석 해결 포인트 BFS 사용 A부터 큐에 삽입 후, 큐에서 값을 꺼내 [*2, 오른쪽에 1추가] 계산 후 큐에 삽입 만약 해당 값이 B보다 크면 큐에 삽입하지 않는다. 큐에 추가 전 담겨져 있는 수 만큼 반복, 후 count 증가 큐에서 값을 꺼냈을 때 값이 B이면 count 반환 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buff..

[백준 11725] 트리의 부모 찾기(JAVA)

CodingTEST 2024. 1. 12. [백준 11725] 트리의 부모 찾기(JAVA) 백준 11725번 문제 - 트리의 부모 찾기 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 분석 트리의 루트를 1이고, 노드끼리 연결 정보를 알려준다. 각 노드의 부모를 구하는 프로그램을 작성하시오. 해결 포인트 BFS 사용 연결 정보를 저장 1을 큐에 넣고 그들의 연결 정보를 알아낸다. 방문하지 않은 노드일 경우, 이 전 값을 해당 값의 부모로 저장 코드 import java.io.*; import java.util.*; public class Main { public static int [] result; public static void main(String[]..

[백준 9019] DSLR (JAVA)

CodingTEST 2024. 1. 6. [백준 9019] DSLR (JAVA) 백준 9019번 문제 - DSLR 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제 분석 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기 존재 D: 값을 두 배로 변경 (2n) 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. S: 갑에서 1 뺀 값으로 변경 (n - 1) n이 0 이라면 9999 가 대신 레지스터에 저장된다. L: n의 각 자릿수를 왼편으로 회전시키기 ( d1, d2, d3, d4 → d2, d3, d4, d1 ) R: n의 각 자릿수..

[백준 16928] 뱀과 사다리 게임(JAVA)

CodingTEST 2024. 1. 2. [백준 16928] 뱀과 사다리 게임(JAVA) 백준 16928번 문제 - 뱀과 사다리 게임 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 문제 분석 게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다. 플레이어는 주사위를 굴려 나온 수만큼 이동 만약 주사위를 굴린 결과가 100번 칸을 넘어간다면 이동할 수 없다. 도착한 칸이 사다리면, 사다리를 타고 ..

[백준 10026] 적록색약 (JAVA)

CodingTEST 2024. 1. 2. [백준 10026] 적록색약 (JAVA) 백준 10026번 문제 - 적록색약 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 분석 적록색약이 아닌 사람이 봤을 때 구역의 수와 적록색약(빨간 초록 구분 못함)이 봤을 때 구역 수를 출력해라. 해결 포인트 BFS 구현 적록색약일 경우 색을 저장하는 이차원배열과, 적록색약일 경우 색을 저장하는 이차원배열을 따로 구현 적록색약일 경우 색을 저장하는 이차원 배열은 빨간색하고 초록색 모두 초록색으로 저장한다. 코드 import java.awt.*; import java.io.*; import java..

[백준 1389] 케빈 베이컨의 6단계 법칙 (JAVA)

CodingTEST 2023. 12. 28. [백준 1389] 케빈 베이컨의 6단계 법칙 (JAVA) 백준 1389번 문제 - 케빈 베이컨의 6단계 법칙 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 문제 분석 사람 수가 정해지고 친구 사이 거리가 1인 조합이 주어진다. 이 때, 나를 제외한 나머지 사람들과의 친구 사이 거리의 합이 가장 적은 사람의 INDEX를 출력해라 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력해라 예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자. 1의 ..

[백준 11403] 경로 찾기 (JAVA)

CodingTEST 2023. 12. 26. [백준 11403] 경로 찾기 (JAVA) 백준 11403번 문제 - 경로 찾기 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 분석 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 자기 자신에게 오는 것도 양수여야지 1로 (돌아서 자기자신으로 돌아와야함 0은 안됨) 해결 포인트 BFS 사용 가운데 대각선 (자기자신 생각) 사이클이 있어야한다. (돌아서 자기자신한테 와야한다) 자기자신을 처음 visit를 true로 하지 말자. 코드 import java.io.*;..

[백준 21736] 헌내기는 친구가 필요해 (JAVA)

CodingTEST 2023. 12. 21. [백준 21736] 헌내기는 친구가 필요해 (JAVA) 백준 21736번 문제 - 헌내기는 친구가 필요해 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 문제 분석 도연이가 다니는 대학의 캠퍼스는 N*M 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해보자. 입력 둘째 줄부터 N개의 줄에는 캠퍼스의 정보들이 주어진다. O는 빈 공간, X는 벽, I는 도연이, P는 사람이다. I가 한 번만 주어짐이 보장된다. 해결 포인트 BFS 구현 ..

[백준 7576] 토마토 (JAVA)

CodingTEST 2023. 12. 13. [백준 7576] 토마토 (JAVA) 백준 7576번 문제 - 토마토 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 분석 창고에 토마토가 격자모양의 상자들에 보관되어있다. 익은 토마토는 하루가 지나면 인접한 곳에 있는 토마토도 익게 한다. 인접한 곳은 위, 아래, 왼쪽, 오른쪽 네 방향에 있는 토마토를 의미 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 익은 토마토 : 1 익지..

[백준 14940] 쉬운 최단거리 (JAVA)

CodingTEST 2023. 12. 13. [백준 14940] 쉬운 최단거리 (JAVA) 백준 14940번 문제 - 쉬운 최단거리 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 문제 분석 지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라. 갈수없는 땅 : 0 갈 수 있는 땅 : 1 목표지점: 2 각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다. 해결 포인트 목표지점까지 거리를 담는 2차원 배열 map의 모든 값을 -1 로..

이전 1 2 3 다음

티스토리툴바