백준

문제 (Gold 3) https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 풀이 탐색을 언제, 어디에서 하는지가 굉장히 중요한 문제! 우선, 더 이상 상태 변경이 없을 때까지 탐색을 반복한다. 탐색 코드 cangoTmp: 탐색하기 전의 상태를 저장해 놓는다. 탐색한 곳에서 스위치를 켤 수 있는 곳의 cango값을 true로 변경한다. BFS 탐색을 돌고, 탐색한 곳에서 map의 List를 돌며 계..

문제 (Gold 5) https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 처음에 단순히 BFS ( 1차원 배열 탐색 ) 으로 풀었더니 당연히! 시간초과가 났다. 그래서 방문하는 인덱스마다의 최단거리를 구하는 다익스트라 알고리즘 사용! 코드 더보기 package shortestPath; import java.util.*; import java.io.*; public class Main_13549_숨바꼭질3{ p..

문제 (Gold 3) https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 마을들인 N에서 목적지 X까지 걸리는 최단거리 -> A 목적지 X에서 각 마을 N까지 걸리는 최단거리 -> B 를 이용해서 왕복 거리의 최단 거리를 구한다! B는 출발지로부터 모든 노드까지의 거리를 구하는 다익스트라 알고리즘을 이용 A의 경우, 모든 노드사이의 거리를 구하려는 플로이드 와샬을 이용하려 하였다. 하지만, 플로이드 와샬의 경우 ..

문제 (Gold 5) https://www.acmicpc.net/problem/2174 2174번: 로봇 시뮬레이션 첫째 줄에 두 정수 A, B가 주어진다. 다음 줄에는 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각 로봇의 초기 위치(x, y좌표 순) 및 방향이 주어진다. 다음 M개의 줄에는 각 명령이 명령을 내리는 순 www.acmicpc.net 풀이 좌표계만 신경쓰면 어렵지 않았던 문제! 나의 경우, 좌상단부터 (0,0) 우하단이(B-1,A-1)가 되도록 좌표를 설정하였다. 여기서 주의해야 할 점은! 입력 또한 x축 좌표부터 입력되므로 바로 [x][y]이렇게 저장하면 오류가 난다. 모든 코드에서 A, B, X, Y, I, J에 헷갈리지 않도록 유의하자! 코드 더보기 package simulat..