본문 바로가기

알고리즘&자료구조/BFS12

프로그래머스 - 게임 맵 최단거리 문제 분석조건1. 상대팀 진영으로 도착하지 못하는 경우 -1 리턴 2. 맵은 n*m 행렬로 주어짐(최대 100*100) 상대방 진영은 무조건 n,m에 위치함 (단, 1*1은 입력으로 주어지지 않음) 3. 자신의 최초 위치도 지나간 칸의 개수에 포함됨 4. 캐릭터는 (1,1)에서 시작로직0.초기값 설정 맵의 크기, 동서남북 방향, 캐릭터가 이동할 큐, 방문처리 1.캐릭터 최초 위치 설정 캐릭터의 시작지점을 큐에 넣고 방문 표시 2.큐에 데이터가 빌때까지 반복문을 돔 캐릭터가 이동할 수 있는 곳이면 이동후 큐에 넣고 방문처리 3.큐가 비면 상대방 진영 확인 dis[n][m]이 0이면 방문을 하지 못했다는 뜻이므로 -1 출력 아니면 dis[n][m] 출력 JAVA 코드import java.util.*;publ.. 2024. 6. 5.
백준 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.

티스토리툴바