✔ 클래스 생성
✔ 뱀의 몸통이 있는 좌표들을 표현할 큐
✔ 처음에는 오른쪽을 보고 있으므로 동->남->서->북 순으로 방향 리스트 초기화
d = {{0,1},{1,0},{0,-1},{-1,0}}
: 'R'이면 dir++ / 'L'이면 dir-- / 직진이면 현재 dir값 그대로해서
ny= y + d[dir] / nx= x+ d[dir]
✔ BFS 살짝
import java.util.*;
class TurnDir{
public TurnDir(int time, char dir) {
this.time = time;
this.direction = dir;
}
public char getDirection() {
return this.direction;
}
public int getTime() {
return this.time;
}
private int time;
private char direction;
}
class Position{
private int y,x;
public Position(int y,int x) {
this.y = y;
this.x = x;
}
public int getY() {
return this.y;
}
public int getX() {
return this.x;
}
}
public class Java0724_1 {
public static int n,k,l;
public static int[][] arr;
public static ArrayList<TurnDir> plan = new ArrayList<TurnDir>();
// 회전 시간, 방향 정보
public static int[][] d = {{0,1},{1,0},{0,-1},{-1,0}};
// 동,남,서,북
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();
arr = new int[n][n];
for(int i=0;i<k;i++)
{
int y = sc.nextInt()-1; // 문제에서 주는 입력값은 좌표 시작점 (1,1)임
int x = sc.nextInt()-1;
arr[y][x] = 1; // 사과가 있는 위치는 1을 가짐
}
l = sc.nextInt();
for(int i=0;i<l;i++) {
int time = sc.nextInt();
//sc.nextLine(); // nextInt 다음 nextLine할 때만
char str = sc.next().charAt(0);
plan.add(new TurnDir(time,str));
}
System.out.print(simulate());
}
private static int simulate() {
int y=0,x=0;
arr[y][x] = 2;
// 뱀이 있는 위치 2/ 사과가 있는 위치/ 그 외 0으로 정하자
int dir =0; // 방향 인덱스
int t=0;
int idx=0; // ArrayList plan의 인덱스
Queue<Position> q = new LinkedList<>();
q.offer(new Position(y, x));
while(true) {
int ny = y+d[dir][0];
int nx = x+d[dir][1];
if(nx>=0&&ny>=0&&ny<n&&nx<n&&arr[ny][nx]!=2) {
// 사과가 없다면 이동 후 꼬리가 위차한 좌표는 큐에서 없애기
if(arr[ny][nx]==0) {
arr[ny][nx]=2;
q.offer(new Position(ny, nx));
Position tail = q.poll();
arr[tail.getX()][tail.getY()] = 0;
}
else if(arr[ny][nx]==1) {
// 사과가 있으면 이동 후에 큐에 이동한 좌표 넣기
arr[ny][nx] = 2;
q.offer(new Position(ny, nx));
}
}
else { // 벽이나 몸에 부딪혔다면
t++;
break;
}
x = nx; y = ny; // 다음 위치로 이동
t++;
if(idx<l&&plan.get(idx).getTime() == t) {
dir= turn(dir,plan.get(idx).getDirection());
idx++;
}
}
return t;
}
public static int turn(int dir,char direction) {
if(direction == 'L')
dir = (dir==0)? 3:dir-1;
else
dir = (dir+1)%4;
return dir;
}
}
✔ 각 기둥/보 설치하고 구조물자체!!를 검사하고 불가능하면 해당 기둥/보 삭제하기/ 각 기둥/보 삭제하고 구조물 자체!!를 검사하고 불가능하면 해당 기둥/보 다시 설치하기!
✔ 설치하기 전 해당 기둥/보 설치가 가능한지 알아보고 가능하면 새로운 2차원 배열에 하나씩 설치하는 방법은 예외처리가 많음. 위의 방법이 비효율적이더라도 build_frame의 최대수가 1000이기에 가능함
# 현재 설치된 구조물이 '가능한' 구조물인지 확인하는 함수
def possible(answer):
for x, y, stuff in answer:
if stuff == 0: # 설치된 것이 '기둥'인 경우
# '바닥 위' 혹은 '보의 한쪽 끝 부분 위' 이거나
if y == 0 or [x - 1, y, 1] in answer or [x, y, 1] in answer:
continue
# '다른 기둥 위'라면 정상
if [x, y - 1, 0] in answer:
continue
return False
elif stuff == 1: # 설치된 것이 '보'인 경우
# '한쪽 끝부분이 기둥 위' 이거나
if [x, y - 1, 0] in answer or [x + 1, y - 1, 0] in answer:
continue
# '양쪽 끝부분이 다른 보와 동시에 연결'이라면 정상
if [x - 1, y, 1] in answer and [x + 1, y, 1] in answer:
continue
return False
return True
def solution(n, build_frame):
answer = []
for frame in build_frame:
x, y, stuff, operate = frame
if operate == 0: # 삭제하는 경우
answer.remove([x, y, stuff]) # 일단 삭제를 해본 뒤에
if not possible(answer): # 가능한 구조물인지 확인
answer.append([x, y, stuff]) # 가능한 구조물이 아니라면 다시 설치
if operate == 1: # 설치하는 경우
answer.append([x, y, stuff]) # 일단 설치를 해본 뒤에
if not possible(answer): # 가능한 구조물인지 확인
answer.remove([x, y, stuff]) # 가능한 구조물이 아니라면 다시 제거
return sorted(answer) # 정렬된 결과를 반환
import java.util.*;
class NodeXYStuff implements Comparable<NodeXYStuff>{
public NodeXYStuff(int x,int y, int stuff) {
this.x = x;
this.y = y;
this.stuff = stuff;
}
private int x,y,stuff;
public int getX() {
return this.x;
}
public int getY() {
return this.y;
}
public int getStuff() {
return this.stuff;
}
// x,y,stuff 순서대로 오름차순 정렬
@Override
public int compareTo(NodeXYStuff o) {
// 우선순위 3, x도 같고 y도 같을 때 : stuff가 기준
if(this.x==o.x&&this.y==o.y)
return Integer.compare(this.stuff, o.stuff);
// 우선순위 2, x가 같을 때 : y가 기준
if(this.x==o.x)
return Integer.compare(this.y, o.y);
// 우선순위 1 , x기준
return Integer.compare(this.x, o.x);
}
}
public class Java0724_2 {
public int[][] solution(int n, int[][] build_frame) {
ArrayList<ArrayList<Integer>> answer = new ArrayList<ArrayList<Integer>>();
for(int[] b:build_frame) {
int x = b[0];
int y = b[1];
int stuff = b[2]; // 기둥/보
int operate = b[3]; // 설치/삭제
if(operate==0) { // 삭제하는 경우// 일단 해당 stuff 삭제하기
int idx =0;
// ArrayList에서 해당 명령이 있는 인덱스 찾기
for(int i=0;i<answer.size();i++) {
if (x==answer.get(i).get(0)&& y==answer.get(i).get(1) &&stuff==answer.get(i).get(2) )
idx = i;
}
ArrayList<Integer> erased = answer.get(idx);
answer.remove(idx);
if(!possible(answer)) // 불가능한 구조물이라면 다시 설치
answer.add(erased);
}
else { // 설치하는 경우 // 일단 설치
ArrayList<Integer> inserted = new ArrayList<Integer>();
inserted.add(x);
inserted.add(y);
inserted.add(stuff);
answer.add(inserted); // 왜 굳이 클래스 객체로 안넣고 이차원 리스트로 이렇게 한거지?
// 삭제하는 경우 삭제를 하고 막상 불가능한 구조물이되면
// 그 stuff를 찾아 다시 추가해야하는데,
// 이때 인덱스로 찾을 수 있도록 리스트를 사용
if(!possible(answer)) // 불가능한 구조물이라면
answer.remove(answer.size()-1); // 삭제
}
}
// x좌표 기준 오름차순 정렬 + x좌표가 같을 경우 y좌표 기준으로 오름차순 정렬
ArrayList<NodeXYStuff> ans = new ArrayList<NodeXYStuff>();
for(int i=0;i<answer.size();i++)
ans.add(new NodeXYStuff(answer.get(i).get(0),answer.get(i).get(1),answer.get(i).get(2)));
Collections.sort(ans);
// 배열로 바꿔 반환
int[][] res = new int[ans.size()][3];
for(int i=0;i<ans.size();i++) {
res[i][0] = ans.get(i).getX();
res[i][1] = ans.get(i).getY();
res[i][2] = ans.get(i).getStuff();
}
return res;
}
public boolean possible(ArrayList<ArrayList<Integer>> answer) {
for(int i=0;i<answer.size();i++) {
int x= answer.get(i).get(0);
int y= answer.get(i).get(1);
int stuff = answer.get(i).get(2);
if(stuff ==0) { // 기둥일 때
boolean check = false;
if(y==0) check = true; // 바닥 위일 때 정상
for(int j=0;j<answer.size();j++) {
// 보의 끝점 끝부분 위 일때 정상
if(x-1==answer.get(j).get(0)&& y==answer.get(j).get(1)&& answer.get(j).get(2)==1)
check = true;
// 보의 시작점 끝부분 위 일때 정상
if(x==answer.get(j).get(0)&& y==answer.get(j).get(1)&& answer.get(j).get(2)==1)
check = true;
// 다른 기둥 위 일때 정상
if(x==answer.get(j).get(0)&& y-1==answer.get(j).get(1)&& answer.get(j).get(2)==0)
check = true;
}
if(!check) return false;
}
else { // 보
boolean check = false;
boolean left = false;
boolean right = false;
for(int j=0;j<answer.size();j++) {
// 보의 시작점이 기둥 위일 때 정상
if(x==answer.get(j).get(0)&&y-1==answer.get(j).get(1)&&answer.get(j).get(2)==0)
check = true;
// 보의 끝점이 기둥 위일때 정상
if(x+1==answer.get(j).get(0)&&y-1==answer.get(j).get(1)&&answer.get(j).get(2)==0)
check = true;
// 보의 시작점이 다른 보의 끝점과 연결되었을 때 정상
if(x-1==answer.get(j).get(0)&&y==answer.get(j).get(1)&&answer.get(j).get(2)==1)
left = true;
// 보의 끝점이 다른 보의 시작점과 연결되었을 때 정상
if(x+1==answer.get(j).get(0)&&y==answer.get(j).get(1)&&answer.get(j).get(2)==1)
right = true;
}
if(left&&right) check = true;
if(!check) return false;
}
}
return true;
}
}