본문 바로가기

728x90

알고리즘&자료구조/BFS11

백준 5427 1. 문제이해 매초마다 불은 상하좌우 빈공간으로 이동 상근이도 매초마다 상하좌우로 이동 가능 벽쪽으로 이동 X, 불이 있는 칸 또는 이제 불이 붙으려는 칸으로 이동 X 빌딩을 탈출하기 위한 최소 시간을 구하기 2. 문제분석 지도(board), 불이동시간(fireMoveT), 상근이 이동시간(playerMoveT) 총 3개의 배열 필요 불이붙는 이동시간을 계산할때 불이 최초에 있는 지점은 0초이고 0이상인 경우 불이 있는 곳이기 때문에 체크 X 상근이의 이동시간(PT)이 불이 붙는시간(FT)보다 무조건 작아야지 이동가능 - 지도에 불과 상근이의 위치를 나타내면서 불이 있는 모든 위치를 큐에 넣음 - 큐를 통해서 지도 전체에 불이 붙는 시간을 모두 계산함 - 상근이의 시작위치를 큐에 넣음 - 상근이가 이동하.. 2024. 5. 1.

백준 7562 문제분석 체스판 길이(size) 8 -> 8 * 8 나이트의 최초 시작 지점(startPoint) 나이트가 이동하려고 하는 칸(endPoint) --> endPoint까지 최소 몇번만에 이동할수 있는지? 0. 시작지점을 큐에 넣음 1. 나이트가 이동할 수 있는 모든 방향을 미리 지정해둠 어떻게 지정할 것인가? 총 8가지 방향 ex) 0,0 기준으로 생각해보기 (x : 행, y : 열) 1. 왼쪽상단 대각선(열감소, 행감소) -> 상(행감소) x -> -2, y -> -1 대각선(열감소, 행감소) -> 좌(열감소) x -> -1, y -> -2 2. 오른쪽상단 대각선(열증가, 행감소) -> 상(행감소) x -> -2, y -> +1 대각선(열증가, 행감소) -> 우(열증가) x -> -1, .. 2024. 4. 30.

백준 7569 1. 문제이해 M은 가로 칸의 수, N은 세로 칸의 수 N개의 줄이 H번 반복하여 입력이 주어짐 ex)5(M), 3(N), 2(H)H 1번 1 0 0 0 11 0 0 0 11 0 0 0 1 H 2번1 0 0 0 11 0 0 0 11 0 0 0 1 2. 문제 분석3차원 배열을 이용해서 토마토 상자의 크기를 구성board[N][M][H] -> 이렇게 크기가 구성되야 함 board[2][2] 이차원 배열일 때 board[0][0]의 뜻은 0행에서 0열을 의미한다.첫번째 세로칸에서 첫번째 가로칸을 가리킨다. board[2][2][2] 삼차원 배열일 때 board[0][0][0]의 뜻은 0행 0열에서 0층에 있는 값을 의미한다. 3. 코드#include#include #include using namespac.. 2024. 4. 28.

백준 10026 1. 문제이해 적록색약이 아닌 사람 기준) 같은 색상이 상하좌우로 인접해 있으면 같은 구역에 속한 것으로 인식 적록색약이 있는 사람 기준) 빨간색과 초록색의 차이를 느끼지 못함 빨강과 초록이 인접해 있어도 동일한 색깔로 인식 2. 문제분석 2개의 이중for문을 돌면서 RGB 구역과 R+G, B 구역을 찾음 큐를 두개 만들어서 구역을 구분함 시간제한은 1초로 최대 100*100 = 10,000번 연산을 수행 2개의 이중 for문이므로 대략 20,000번 연산을 함 O(n*n) 시간복잡도로 풀어도 됨 3. 코드#include#include using namespace std;// define 뒤에 ; 써서 틀림 // #define X first// #define Y secondchar board.. 2024. 4. 27.

이전 1 2 3 다음

728x90

티스토리툴바