승쨩개발공부

나이트는 (2,1),(1,2),(-1,2)(-2,1),   (-2,-1),(-1,-2)(1,-2)(2,-1) 을 이동할 수 있다보드판을 직접 입력할 필요는 없고 Check에 이동거리를 q.front에 + 1씩 저장해주면 된다. 첫쨰줄은 테스트케이스 갯수둘쨰줄은 체스판의 한변의 길이 n(정사각형)셋째줄에는 시작 인덱스넷쨰줄에는 목적지 인덱스를 입력 받으면 된다. 어떻게 풀어야하는지 그림을 한번 보자 그냥 전에 풀었던 BFS처럼 시작지점에서 폰 이동범위 마다 거리를 기록해주면 된다.

각 구역마다 돌면서 R갯수 G갯수 B갯수를 구해서 갯수를구하고그 다음 RG갯수 B갯수를 구하면 된다모든 구역을 돌고 같은 문자만 BFS를 돌고 BFS를 나오게되면 카운트를 증가해주면된다.  이번엔 열 갯수만 입력으로 주어진다.

이번 문제는 t와 2차원 인덱스를 직접 삽입해야해서 아주 조금 변형이 있었다.n,m 위치를 잘 생각하고 풀어야 했었다. 예제2번 그림이런식으로 2개의 지렁이가 나오게 된다.t도 있으니 BFS가 다 끝나고 지렁이를 출력하면 보드판과 체크도 초기화를 해줘야한다.그리고 t가 있을경우 출력하고 열바꿈을 해주자. 이거 안해서 계속 틀렸었다..(\n)

자 수빈이와 동생은 0 수빈이는 앞과 뒤 로 이동할수있고 현재위치 * 2 의 위치로 이동할수있다. 이걸 생각해보면 배열이고 이동거리를 저장해야하니 BFS로 풀 수 있겠다 라는 생각이 들것이다. 일단 배열을 모두 -1로 초기화해주고 수빈이의 초기위치를 0으로 만든다 그리고 Queue에 집어넣는다배열을 모두 -1로 초기화 했으니 수빈이의 거리가 -1이 아니라 양수로 바뀔떄까지 반복을 돌리면 되겠다. 그림으로 한번 거리를 봐보자. .5번은 수빈이의 초기 위치고 17번은 동생의 위치이다.5 -> 10 -> 9 -> 18 -> 17 로 간다면 4초가 걸리게 될것이다.

이번엔 불과 지훈이가 동시에 있다 지훈이가 불에 타기전에 탈출을 할 수 있는지 체크를 해야한다. 현재 보기 TK가 4,4밖에 없으니 5,5로 예를들어 설명을 해보겠다.열과 행이 5,5인 Board가 다음과 같이 입력이 주어졌다고 치겠다. 저번에 토마토 문제처럼 전부 거리를 -1로 만들고지훈이 위치를 거리 0으로 만들고 시작해보자 지훈이의 이동 거리의 경로가 불번짐에 이동 거리보다 적기떄문에 무사히 탈출이 가능하다. 그럼 이렇게 그려보면 유추가 가능하다큐를 두개(지훈,불),거리측정을 두개(지훈,불) DFS를 두번(지훈,불) 돌리고 지훈이 DFS에서 불번짐 거리를 재면 되겟구나?범위를 벗어나면 탈출이고 큐가 빌떄까지 범위를 못 벗어나면 탈출을 못 하는구나?  여기서 중요한 포인트는 Distance가 벽도 -..

일단 상하좌우로 퍼져나가니 BFS로 풀수있다는걸 눈치를 챌 수 있다.하지만 여지껏 풀었던 BFS문제와 다르게 시작점이 여러개일수있다 TK 3번을 보자. 이렇게 input이 들어오게 되는데.-1이 있는곳을 제외하고 퍼지면서 1씩 증가해야하니이런식으로 되어야 할것이다. 근데 출력에서 0 = 처음부터 모두 토마토가 익어있는거고, -1은 모두 익지 못하는 상황이고,나머지는 토마토가 익을 수 있는 일 수를 출력하는 것 이다. 그러면 여기서 input을 보면 생각을 해 볼 수 있다.그러면 상하좌우로 갈 수 있는 부분만 -1로 미리 표시를 해놓으면 되지 않을까?이런식으로 말이다.-1만 움직일 수 있도록 해놓고 만약 -1일이 모두 상하좌우로 이어져 있지 않아서 BFS를 하고나서도 -1이 남아있다면?모두 익지 못하는 상..