문제 7562번 (bfs)
: 나이트는 몇 번 움직이면 칸으로 이동할 수 있을까?
[입력]
: 첫째 줄에는 테스트 케이스 묶음 개수
: 테스트 케이스 한묶음 당 3개의 줄이 있다
: 첫째 줄에는 체스판의 한 변의 길이 (크기 1 × 1)
: 둘째 줄에는 나이트가 현재있는 칸 위치
: 셋째 줄에는 나이트가 이동하려는 칸 위치
[출력]
: 각 테스트 케이스 묶음마다 나이트의 최소 이동 횟수 출력
[설명]
BFS
현재 정점에 연결된 가까운 점들부터 탐색
Queue를 사용해서 구현
java.awt.Point
- Point 클래스는 좌표 상의 위치를 나타내는데 사용
- x와 y좌표값을 저장하기 위한 멤버변수를 갖는다
| Field Summary | ||
| Modifier and Type | Field and Description | 설명 |
| int | x | x좌표 |
| int | y | y좌표 |
| 메소드 | 설명 |
| void setLocation(int x, int y) | x, y좌표의 위치값을 설정 |
| Point getLocation() | 현재 위치의 x, y좌표값을 반환 |
출처 : https://codedragon.tistory.com/6044
[문제 과정]
| X | Y | |
| 좌표 | 1 2 2 1 - 1 - 2 - 2 - 1 |
- 2 - 1 1 2 2 1 - 1 - 2 |
| 방향 | 8 가지 | |
출처 : https://yurimac.tistory.com/47
위 그림은 체스가 움직일 수 있는 방향을 표현한 것이다
실제로 체스판이나 체스가 저모양 그대로 고정되어 있지 않다는 점 주의하기
[코드1]
import java.io.*;
import java.awt.*;
import java.util.*;
public class Main{
static int T,size,x,y,x1,y1;
static int arr[][];
static boolean visit[][];
static int result=0;
static int dx[] = {1, 2, 2, 1, -1, -2, -2, -1 };
static int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2 };
static Queue<Point> q = new LinkedList<>();
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
T=Integer.parseInt(br.readLine());
while(T-->0){
size=Integer.parseInt(br.readLine());
arr=new int[size][size];
visit= new boolean[size][size];
st= new StringTokenizer(br.readLine());
x=Integer.parseInt(st.nextToken());
y=Integer.parseInt(st.nextToken());
st= new StringTokenizer(br.readLine());
x1=Integer.parseInt(st.nextToken());
y1=Integer.parseInt(st.nextToken());
bfs();
System.out.println(arr[x1][y1]);
}
}
static void bfs(){
q.add(new Point(x,y));
visit[x][y]= true;
while(!q.isEmpty()){
Point p = q.poll();
for(int i =0; i<8;i++){
int nx = p.x+dx[i];
int ny = p.y+dy[i];
if(nx>=0 && ny>=0 && nx < size && ny <size){
if(!visit[nx][ny]){
q.add(new Point(nx,ny));
arr[nx][ny] = arr[p.x][p.y] +1;
visit[nx][ny] =true;
}
}
}
}
}
}
[해설]
: import java.awt.*;
: static int T,size,x,y,x1,y1; 입력값
static int arr[][]; 배열 좌표
static boolean visit[][]; 방문기록
static int dx[] = {1, 2, 2, 1, -1, -2, -2, -1 }; 8개의 초록칸 x 좌표
static int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2 }; 8개의 초록칸 y 좌표
static Queue<Point> q = new LinkedList<>(); 큐 설정
: T=Integer.parseInt(br.readLine()); 첫째줄 입력 (테스트 케이스 묶음수)
: while(T-->0){ 테스트 케이스만큼 묶음 생성
size=Integer.parseInt(br.readLine()); 체스판 크기
arr=new int[size][size]; 체크판 크기만큼 배열좌표 생성
visit= new boolean[size][size]; 방문기록 생성
st= new StringTokenizer(br.readLine()); 한 테스트 케이스 묶음의 두번째 줄
x=Integer.parseInt(st.nextToken()); 현재 위치 x좌표
y=Integer.parseInt(st.nextToken()); 현재 위치 y좌표
st= new StringTokenizer(br.readLine()); 한 테스트 케이스 묶음의 첫번째 줄
x1=Integer.parseInt(st.nextToken()); 이동할 위치 x좌표
y1=Integer.parseInt(st.nextToken()); 이동할 위치 y좌표
bfs(); bfs 호출
System.out.println(arr[x1][y1]); 최종 목적지인 x1, y1를 bfs에 넣어 나온 총 횟수 출력
}
: static void bfs(){
q.add(new Point(x,y)); 위에서 입력값으로 받은 현재 위치 좌표 x,y 큐에 넣기
visit[x][y]= true; 해당위치 방문처리
while(!q.isEmpty()){ 큐가 빌 때까지
Point p = q.poll(); 큐에서 뺀 값들 p에 저장
for(int i =0; i<8;i++){ 초록칸의 8방향 탐색
int nx = p.x + dx[i]; 새로 이동할 x 좌표 = 큐에서 뺀 현재 x값 + 갈 수 있는 x 방향
int ny = p.y + dy[i]; 새로 이동할 y 좌표 = 큐에서 뺀 현재 y값 + 갈 수 있는 y 방향
if(nx>=0 && ny>=0 && nx < size && ny <size){ 체스 이동이 0 ~ size (체스판만큼) 으로 제한
if(!visit[nx][ny]){ 방문처리가 안되어 있다면
q.add(new Point(nx,ny)); 큐에 새로운 현위치 저장
arr[nx][ny] = arr[p.x][p.y] +1; arr배열 값 지정한 적 X (즉 0부터 시작) → 횟수 = 0+1
visit[nx][ny] =true; 해당 위치 방문처리하기
}
}
}
}
[코드2]
import java.io.*;
import java.util.*;
import java.awt.*;
public class Main{
static int dx[] = {1, 2, 2, 1, -1, -2, -2, -1 };
static int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2 };
static int count,I;
static Point start, end;
static boolean visit[][];
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
while(T-->0){
I = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
start = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
st = new StringTokenizer(br.readLine());
end = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
count =0;
visit = new boolean[I][I];
System.out.println(bfs(start));
}
}
static int bfs(Point start){
Queue <Point> q = new LinkedList<>();
q.add(start);
visit[start.x][start.y]=true;
while(!q.isEmpty()){
int size = q.size();
for(int j=0;j<size;j++){
Point p = q.poll();
if(p.x==end.x&&p.y==end.y){
return count;
}
for(int i=0; i<8;i++){
int nextx=p.x+dx[i];
int nexty=p.y+dy[i];
if(0<=nextx&&nextx<I && 0<=nexty&&nexty<I && !visit[nextx][nexty]){
q.add(new Point(nextx,nexty));
visit[nextx][nexty]=true;
}
}
}
count++;
}
return count;
}
}
[짧은 설명]
- 입력 자체를 Point 함수를 통해 받는다
- 한바퀴 돌 때마다 큐에서 몇개의 좌표를 받을지 예상할 수 없다 → 큐사이즈 매번 저장하기
(갈 수 있는 방향이 8개이므로 8번 이동 가능하지만 음수가 아니며, 체스판 안에 포함되어있고,
아직 방문하지 않은 조건에 포함되는 좌표들이 몇 개일지 모르므로)
- count++는 큐에 추가하는 시점이 아닌 큐에서 빼서 모든 좌표를 확인하고 난 다음에 넣어줘야 한다
즉 내가 1회에 갈 수 있는 방향이 최대 8개인데 여러개의 좌표를 하나씩 대입해보며 종료조건이 되는지 확인한다
좌표마다 count 되는 것이 아니라 이 여러개의 좌표 중 내가 선택해서 가야할 길은 딱 하나의 좌표이기 때문에
count를 뒤에 배치하는 것이다
[해설]
: import java.awt.*;
: static int count,I; 입력값
static Point start, end; 현재좌표, 도착좌
static boolean visit[][]; 방문기록
static int dx[] = {1, 2, 2, 1, -1, -2, -2, -1 }; 8개의 초록칸 x 좌표
static int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2 }; 8개의 초록칸 y 좌표
: int T=Integer.parseInt(br.readLine()); 첫째줄 입력 (테스트 케이스 묶음수)
: while(T-->0){ 테스트 케이스만큼 묶음 생성
I = Integer.parseInt(br.readLine()); 체스판 크기
visit= new boolean[size][size]; 방문기록 생성
st= new StringTokenizer(br.readLine());
start = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())); 현위치
st= new StringTokenizer(br.readLine());
end = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())); 목표위치
visit = new boolean[I][I]; 매 테스트 케이스마다 방문기록 초기화
count =0; 카운트 초기화
System.out.println(bfs(start)); 출력
}
: static int bfs(Point start){
Queue <Point> q = new LinkedList<>(); 큐생성
q.add(start); 현재 위치 좌표 큐에 넣기
visit[start.x][start.y]=true; 해당위치 방문처리
while(!q.isEmpty()){ 큐가 빌 때까지
int size = q.size(); 매번 큐사이즈 저장하고 시작
for(int j=0;j<size;j++){ 큐사이즈 만큼 반복
Point p = q.poll(); 큐에서 뺀 값들 p에 저장
if(p.x==end.x&&p.y==end.y){ 종료조건
return count; count 출력
}
for(int i=0; i<8;i++){
int nextx=p.x+dx[i]; 새로 이동할 x 좌표 = 큐에서 뺀 현재 x값 + 갈 수 있는 x 방향
int nexty=p.y+dy[i]; 새로 이동할 y 좌표 = 큐에서 뺀 현재 y값 + 갈 수 있는 y 방향
if(0<=nextx&&nextx<I && 0<=nexty&&nexty<I && !visit[nextx][nexty]){
q.add(new Point(nextx,nexty)); 큐에 새로운 현위치 저장
visit[nextx][nexty]=true; 해당 위치 방문처리
}
}
}
count++;
}
return count;
}
이제 풀어보러 갈께요 :)
7562번: 나이트의 이동
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수
www.acmicpc.net
* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *
'Baekjoon > [5] DFS & BFS' 카테고리의 다른 글
| [백준] 7569번 토마토 JAVA (자바) 풀이 (1) | 2023.09.21 |
|---|---|
| [백준] 11725번 트리의 부모 찾기 JAVA (자바) 풀이 (0) | 2023.09.20 |
| [백준] 11724번 연결 요소의 개 JAVA (자바) 풀이 (0) | 2023.09.16 |
| [백준] 4963번 섬의 개수 JAVA (자바) 풀이 (0) | 2023.09.15 |
| [백준] 1260번 DFS & BFS JAVA (자바) 풀이 (0) | 2023.09.14 |
