Heecheol's blog

문제 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 풀이 이 문제에서 엘리베이터는 상하좌우로 움직이는 것이 아닌 위아래로만 움직인다. 따라서 이전에 dx, dy 대신 dy만 [u,-d]로 선언해주었다. floor는 전체 층수보다 1더 크게 만든 뒤 -1로 채워주었다. 전체 층수보다 1크게 만든 이유는 floor[층수 - 1]이 아닌 [층수]로 이용하기 위해서다. 큐에 현재 있는 층을 넣은 뒤에 while문을 이용해 bfs를 돌려준다. 현재 층에서 u, -..

문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 기본적인 BFS문제였다. 입력대로 house라는 변수를 만든 뒤에 반복문을 통해 1을 만났을때 bfs를 돌리도록 하였다. 그렇게되면 1을 만난 자리에서 dx,dy에 의해 상하좌우로 한칸씩 증가해가면서 1인 자리를 전부 찾게 될 것이고, 이때마다 area에 1을 더해주어 넓이를 구할 수 있게하였다. 또한, 하나의 단지를 다 탐색했다면 다음 탐색을 시작할때 for문을 통해 1을 찾게 될 것이..

문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 풀이 기본적인 BFS문제였다. paper라는 변수를 만들고 주어진 입력을 받아 반복문을 통해 직사각형이 있는 곳을 1로 표시해주었다.(나머지는 0) 이후에 bfs를 돌리면되는데, paper[newX][newY]가 0인지만 확인해준뒤 맞다면 바로 큐에 넣어주었다. while문 안에서 queue.removeFirst()를 할 때마다 이어져있는 넓이를 구하는 것이므로 area에..

문제 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 풀이 불! 문제와 아예 똑같은 것 같다. https://heecheol.tistory.com/143 [Swift] 백준_불!(4179) 문제 https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동 heec..

문제 https://www.acmicpc.net/problem/25330 25330번: SHOW ME THE DUNGEON 올 여름 출시된 RPG 게임 "SHOW ME THE DUNGEON"은 주인공 시루가 몬스터에게 침략당한 마을을 구하는 내용의 게임이다. 배경이 되는 나라는 $0, 1, 2, \cdots, N$번의 번호가 붙어있는 $N+1$개의 마을로 이루 www.acmicpc.net 풀이 처음에 DFS를 이용해 배열의 크기가 1인 것부터 n개인 것까지 미리 모두 구한 뒤에 각각의 케이스별로 계산해서 결과를 구했었다. 이렇게 했을때 시간 초과가 나와서 방법을 더 고민하다가 배열에서 k보다 큰 것들은 미리 빼놓으면 dfs를 돌릴때 많이 줄어들 수도 있다고 생각해서 다시 시도해봤는데 역시 큰 차이가 없어..