문제 분석
조건
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.*;
public class Main {
static public int solution(int[][] maps) {
int[][] dis = new int[100][100]; // default는 0, 방문한 칸은 1이상으로 체크
int[] dx = {-1,1,0,0};
int[] dy = {0,0,-1,1};
Queue<int[]> q = new LinkedList<>();
// add 함수를 사용해도 되지만, 동적 자료구조인 LinkedList는 capacity에 따라서 메모리 크기가 확장되는데
// add를 했을 때 capacity가 꽉차서 데이터를 추가할 수 없는 경우 예외를 발생시킴 offer의 경우는 예외를 발생시키지 않고 false를 리턴함
// q.add(new int[] {0,0});
q.offer(new int[] {0,0});
dis[0][0] = 1;
while(!q.isEmpty()) {
int[] cur = q.poll();
int row = cur[0];
int col = cur[1];
// 캐릭터 이동 방향 체크
for(int dir=0;dir<4;dir++) {
int nx = row + dx[dir];
int ny = col + dy[dir];
// 맵을 벗어나거나 벽 또는 방문했으면 이동 X
if(nx < 0 || nx >= maps.length || ny < 0 || ny >= maps[0].length) continue;
if(maps[nx][ny] == 0 || dis[nx][ny] >= 1) continue;
q.add(new int[] {nx,ny});
dis[nx][ny] = dis[row][col] + 1;
}
}
int answer = dis[maps.length-1][maps[0].length-1];
if(dis[maps.length-1][maps[0].length-1] == 0) {
answer = -1;
}
return answer;
}
public static void main(String[] args) {
}
}
Q) 큐를 링크드 리스트로 구현하는 이유?
링크드 리스트의 특징)
1. 각 노드는 이전 노드와 다음 노드에 대한 참조(주소)를 가지기 때문에 더 많은 메모리를 사용함
2. 삽입과 삭제가 양 끝단에서 이루어지는 경우 O(1)의 시간 복잡도를 가지기 때문에 BFS 알고리즘에서 큐를 사용하는데 있어 이점이 된다.
ArrayList로 큐를 구현하는 경우 큐에서 맨 앞의 요소를 제거하는 경우에 있어서 ArrayList는 데이터들을 메모리상에 연속적으로 배치하기 때문에 모든 요소들이 한 칸씩 이동하게 되면서 레퍼런스(참조)인 인덱스가 바뀌기 때문에 비효율적이다. 그래서 메모리들이 연속적으로 배치되지 않아도 되는 LinkedList를 이용해서 큐를 구현하는 방식이 효과적이다.
ArrayList는 인덱스를 통해 해당 요소의 접근은 빠르지만, 큐에서는 양 끝단에 있는 요소들만 접근하기 때문에 굳이ArrayList를 사용하는 것보다 LinkedList를 사용하는 것이다.
Q) 레퍼런스와 주소의 차이
레퍼런스 : 생성된 객체의 메모리 주소를 간접적으로 참조하는 변수
레퍼런스 변수가 가지고 있는 주소는 실제 메모리 주소가 아닌 추상화된 개념으로 자바에서는 레퍼런스 변수를 통해 객체의 메소드나 변수에 접근한다.
주소 : 객체가 메모리 내에 저장된 실제 물리적 위치
** C같은 java보다 저수준의 언어는 주소를 사용해서 실제 물리적 위치를 접근할 수 있다는 말이고, java에서 실제 물리적주소는 JVM이 관리하며 프로그래머는 실제 물리적 주소를 가지고 있는게 아니라 추상적인? 주소를 가지고 있다?
