본문 바로가기

분류 전체보기

 (239)
[Baekjoon] 섬의 개수 👀 문제 설명 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다. 입력의 마지막 줄에는 0이 두 개 주어진다. 출력 각 테스트 케이스에 대해서, 섬의 ..
[Baekjoon] 마법사 상어와 파이어볼 👀 문제 설명 문제 어른 상어가 마법사가 되었고, 파이어볼을 배웠다. 마법사 상어가 크기가 N×N인 격자에 파이어볼 M개를 발사했다. 가장 처음에 파이어볼은 각자 위치에서 이동을 대기하고 있다. i번 파이어볼의 위치는 (ri, ci), 질량은 mi이고, 방향은 di, 속력은 si이다. 위치 (r, c)는 r행 c열을 의미한다. 격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다. 파이어볼의 방향은 어떤 칸과 인접한 8개의 칸의 방향을 의미하며, 정수로는 다음과 같다. 7 0 1 6 2 5 4 3 마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음이 일들이 일어난다. 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다...
[Baekjoon] 내리막 길 👀 문제 설명 문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다. 지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하..
[Baekjoon] 마법사 상어와 비바라기 👀 문제 설명 문제 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 N×N인 격자에서 연습하려고 한다. 격자의 각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다. 바구니에 저장할 수 있는 물의 양에는 제한이 없다. (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고, A[r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다. 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는..
[Baekjoon] 모노미노도미노 2 👀 문제 설명 문제 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, y는 열을 의미한다. 빨간색, 파란색, 초록색 보드가 사용하는 좌표는 그 색으로 그림에 적혀있다. 모노미노도미노 게임 보드 이 게임에서 사용하는 블록은 타일 하나 또는 두 개가 가로 또는 세로로 붙어있는 형태이다. 아래와 같이 세 종류가 있으며, 왼쪽부터 순서대로 크기가 1×1, 1×2, 2×1 이다. 모노미노도미노 게임에서 사용하는 블록 블록을 놓을 위치를 빨간색 보드에서 선택하면, 그 위치부터 초록색 보드로 블록이 이동하고, 파란색 보드로 블록이 이동한다. 블록의 이동은 다른 블록을 만나거..
[SWEA] 특이한 자석 👀 문제 설명 문제 로그인해야 문제를 볼 수 있다. ✍🏻풀이 4개의 자석의 정보를 저장하는 LinkedList 배열을 만들고 이를 사용해서 회전시키면 된다. LinkedList[] magnet은 각각의 4개의 자석 정보를 담는다. magnet[0]은 1번 자석, magnet[1]은 2번 자석, magnet[2]는 3번, magnet[3]은 4번의 정보를 저장한다. 회전 시킬 자석과 방향을 입력받아 각각 standardNum과 rotateDir에 저장한다. checkMagnets 메서드는 standardNum 자석을 회전시켰을 때, 다른 자석들이 회전하는지 확인해주는 메서드이다. standardNum을 기준으로 오른쪽 자석들이 회전해야 하는지 확인할 때는, 기준 자석의 2번 자성 정보와 확인할 자석의 6번..
[SWEA] 최장 증가 부분 수열 👀 문제 설명 문제 로그인해야 문제를 볼 수 있다. ✍🏻풀이 DP를 사용해 각 자리까지의 최장 증가 수열을 저장한다. nums는 입력받은 숫자 배열이고, dp는 각 자리까지의 최장 증가 수열을 저장하는 배열이다. dp[0]은 제일 앞에 있는 값이므로 1로 두고 시작한다. i = 1 부터 N - 1까지 접근해 각 자리의 최장 증가 수열을 구한다. 현재자리의 최장 증가 수열은 나의 앞에서 나보다 작은 애들 중의 최장 증가 수열 + 1이다. 예를 들어, nums가 1, 3, 2, 5, 4일 경우 dp[3]을 구하려면 인덱스 0부터 2까지 돌면서 나보다 작은 애들의 최장 증가 수열의 최댓값을 구한다. nums[0], nums[1], num[2] 모두 5보다 작으므로, 얘들의 dp값을 비교하여 최댓값을 가져온다...
[SWEA] 탈주범 검거 👀 문제 설명 문제 로그인해야 문제를 볼 수 있다. ✍🏻풀이 BFS를 사용해 각 칸까지 이동하는데 걸리는 시간을 구한다. map[r][c]는 지하 터널의 상태를 저장하는 배열이고, time[r][c]는 (r, c)까지 이동하는데 걸리는 시간을 저장하는 배열이다. 이 배열들을 사용해 BFS를 구현하면 된다. map[r][c]가 터널 구조물이라면(1~7이라면) 타입에 맞게 인접한 nextX, nextY를 구해준다. isPossibleScope은 (nextX, nextY)가 이동할 수 있는 곳인지 확인하는 메서드이다. (nextX, nextY)가 범위를 벗어나거나, 이미 방문한 곳이거나, 이동할 수 없는 곳(구조물이 없는 경우. 즉, map[nextX][nextY] = 0)이라면 false를, 아니라면(이동할..

티스토리툴바