'Dummy' ๋ผ๋ ๋์ค๊ฒ์์ด ์๋ค. ์ด ๊ฒ์์๋ ๋ฑ์ด ๋์์ ๊ธฐ์ด๋ค๋๋๋ฐ, ์ฌ๊ณผ๋ฅผ ๋จน์ผ๋ฉด ๋ฑ ๊ธธ์ด๊ฐ ๋์ด๋๋ค. ๋ฑ์ด ์ด๋ฆฌ์ ๋ฆฌ ๊ธฐ์ด๋ค๋๋ค๊ฐ ๋ฒฝ ๋๋ ์๊ธฐ์์ ์ ๋ชธ๊ณผ ๋ถ๋ชํ๋ฉด ๊ฒ์์ด ๋๋๋ค.
๊ฒ์์ NxN ์ ์ฌ๊ฐ ๋ณด๋์์์ ์งํ๋๊ณ , ๋ช๋ช ์นธ์๋ ์ฌ๊ณผ๊ฐ ๋์ฌ์ ธ ์๋ค. ๋ณด๋์ ์ํ์ข์ฐ ๋์ ๋ฒฝ์ด ์๋ค. ๊ฒ์์ด ์์ํ ๋ ๋ฑ์ ๋งจ์ ๋งจ์ข์ธก์ ์์นํ๊ณ ๋ฑ์ ๊ธธ์ด๋ 1 ์ด๋ค. ๋ฑ์ ์ฒ์์ ์ค๋ฅธ์ชฝ์ ํฅํ๋ค.
๋ฑ์ ๋งค ์ด๋ง๋ค ์ด๋์ ํ๋๋ฐ ๋ค์๊ณผ ๊ฐ์ ๊ท์น์ ๋ฐ๋ฅธ๋ค.
- ๋จผ์ ๋ฑ์ ๋ชธ๊ธธ์ด๋ฅผ ๋๋ คย ๋จธ๋ฆฌ๋ฅผย ๋ค์์นธ์ ์์น์ํจ๋ค.
- ๋ง์ฝ ์ด๋ํ ์นธ์ ์ฌ๊ณผ๊ฐ ์๋ค๋ฉด, ๊ทธ ์นธ์ ์๋ ์ฌ๊ณผ๊ฐ ์์ด์ง๊ณ ๊ผฌ๋ฆฌ๋ ์์ง์ด์ง ์๋๋ค.
- ๋ง์ฝ ์ด๋ํ ์นธ์ ์ฌ๊ณผ๊ฐ ์๋ค๋ฉด, ๋ชธ๊ธธ์ด๋ฅผ ์ค์ฌ์ ๊ผฌ๋ฆฌ๊ฐ ์์นํ ์นธ์ ๋น์์ค๋ค. ์ฆ, ๋ชธ๊ธธ์ด๋ ๋ณํ์ง ์๋๋ค.
์ฌ๊ณผ์ ์์น์ ๋ฑ์ ์ด๋๊ฒฝ๋ก๊ฐ ์ฃผ์ด์ง ๋ ์ด ๊ฒ์์ด ๋ช ์ด์ ๋๋๋์ง ๊ณ์ฐํ๋ผ.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ๋ณด๋์ ํฌ๊ธฐ N์ด ์ฃผ์ด์ง๋ค. (2 โค N โค 100) ๋ค์ ์ค์ ์ฌ๊ณผ์ ๊ฐ์ย K๊ฐ ์ฃผ์ด์ง๋ค. (0 โค K โค 100)
๋ค์ K๊ฐ์ ์ค์๋ ์ฌ๊ณผ์ ์์น๊ฐ ์ฃผ์ด์ง๋๋ฐ, ์ฒซ ๋ฒ์งธ ์ ์๋ย ํ, ๋ ๋ฒ์งธ ์ ์๋ย ์ด ์์น๋ฅผ ์๋ฏธํ๋ค.ย ์ฌ๊ณผ์ ์์น๋ ๋ชจ๋ ๋ค๋ฅด๋ฉฐ, ๋งจ ์ ๋งจ ์ข์ธก (1ํ 1์ด) ์๋ ์ฌ๊ณผ๊ฐ ์๋ค.
๋ค์ ์ค์๋ ๋ฑ์ ๋ฐฉํฅ ๋ณํ ํ์ L ์ด ์ฃผ์ด์ง๋ค. (1 โค L โค 100)
๋ค์ L๊ฐ์ ์ค์๋ ๋ฑ์ ๋ฐฉํฅ ๋ณํ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋๋ฐ, ย ์ ์ X์ ๋ฌธ์ C๋ก ์ด๋ฃจ์ด์ ธ ์์ผ๋ฉฐ, ๊ฒ์ ์์ ์๊ฐ์ผ๋ก๋ถํฐ X์ด๊ฐ ๋๋ ๋ค์ ์ผ์ชฝ(C๊ฐ 'L') ๋๋ ์ค๋ฅธ์ชฝ(C๊ฐ 'D')๋ก 90๋ ๋ฐฉํฅ์ ํ์ ์ํจ๋ค๋ ๋ป์ด๋ค. X๋ 10,000 ์ดํ์ ์์ ์ ์์ด๋ฉฐ, ๋ฐฉํฅ ์ ํ ์ ๋ณด๋ X๊ฐ ์ฆ๊ฐํ๋ ์์ผ๋ก ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ๊ฒ์์ด ๋ช ์ด์ ๋๋๋์ง ์ถ๋ ฅํ๋ค.
๐ก ๋ฑ์ ์์น(๋ฑ์ ๋จธ๋ฆฌ๋ถํฐ ๊ผฌ๋ฆฌ๊น์ง์ ์์น)๋ฅผ ์๋ ค์ค queue๋ฅผ ํ ๋น
๐ก rotateํ๋ ์๊ฐ์ด ๋๋ฉด ๋ฏธ๋ฆฌ ์ ์ธํด๋์ d(๋ฐฉํฅ) ๋ณ์๋ฅผ ํตํด ๋ฑ์ ์์น๋ฅผ ์กฐ์
๐ก n์ด๊ฐ ์ง๋ํ, rotateํ๋ ค๋ฉด D๋ idx+1๋ฅผ ํตํด d๋ฅผ ์กฐ์ ํ๊ณ , L์ idx-1์ ํตํด ์กฐ์ ํจ
( ์์๋ ์ค๋ฅธ์ชฝ ์๋ ์ผ์ชฝ ์๋ก ์ ์ฅ๋์ด ์๊ณ D๊ฐ ๋์ค๋ฉด ๊ทธ๋๋ก ๋๊ณ , L์ด ๋์ค๋ฉด ๋ฐ๋๋ก ๋๋ฉด ๋จ )
๐ก ๋ฑ์ ๋จธ๋ฆฌ๊ฐ ๊ฐ ์นธ์ ์์น nx, ny๋ฅผ ์
๋ฐ์ดํธํจ
๐ก ๋ฒฝ์ ๋ถ๋ชํ๊ฑฐ๋ ์์ ์ ๋ชธ๊ณผ ๋ง๋ฟ์ผ๋ฉด while๋ฌธ break ํจ
( map์์ 1์ ์ฌ๊ณผ ์์น, -1์ ๋ฑ์ ์์น, 0์ ์๋ฌด๊ฒ๋ ์์์ ๋ํ๋ )
๐ก tmp์ nx, ny ์นธ์ ๊ฐ์ ๋ฐ์์จ ํ, ๋ฑ์ ๋จธ๋ฆฌ์นธ์ ํ์ ๋ฃ๊ณ map๋ -1์ ํด์ค
๐ก tmp๊ฐ 1์ด ์๋๋ฉด, ์ฌ๊ณผ๊ฐ ์๋ ์นธ์ผ๋ก ๋ฑ์ ๊ผฌ๋ฆฌ๊ฐ ์๋ ์นธ์ ์ผ๋ฐ ์นธ์ผ๋ก ๋ง๋ค์ด์ค
( snake ํ์ ๊ฐ์ฅ ์ฒ์์ ์๋ ๊ฒ์ด ๋ฑ์ ๊ผฌ๋ฆฌ๊ฐ ์๋ ์นธ์ / ์ด๋ฅผ ์ ๊ฑฐํ๊ณ map ์์น์ 0์ ๋ฃ์ด์ค )
๐ก ์๊ฐ์ ++ ํด์ค
Queue<Node> snake = new LinkedList<>();
static int[] dx = {0,1,0,-1};
static int[] dy = {1,0,-1,0};
...
int d = 0;
...
if(idx < r.length) {
if(sec-1 == r[idx].x) {
if(r[idx].c == 'L') {
if(d == 0) d = 3;
else d--;
} else {
d = (d+1)%4;
}
idx++;
}
}
nx = nx + dx[d];
ny = ny + dy[d];
if(nx < 1 || nx >= n+1 || ny < 1 || ny >= n+1 || map[nx][ny] == -1)
break;
int tmp = map[nx][ny];
map[nx][ny] = -1;
snake.add(new Node(nx,ny));
if(tmp != 1) {
Node tmp2 = snake.poll();
map[tmp2.x][tmp2.y] = 0;
}
sec++;
import java.io.*;
import java.util.*;
public class BOJ_3190 {
static int n, k;
static int[][] map;
static Rotate[] r;
static int[] dx = {0,1,0,-1};
static int[] dy = {1,0,-1,0};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
k = Integer.parseInt(br.readLine());
map = new int[n+1][n+1];
for(int i=0; i<k; i++) {
String[] s = br.readLine().split(" ");
map[Integer.parseInt(s[0])][Integer.parseInt(s[1])] = 1;
}
r = new Rotate[Integer.parseInt(br.readLine())];
for(int i=0; i<r.length; i++) {
String[] s = br.readLine().split(" ");
r[i] = new Rotate(Integer.parseInt(s[0]), s[1].charAt(0));
}
dummy();
}
static void dummy() {
Queue<Node> snake = new LinkedList<>();
snake.add(new Node(1,1));
map[1][1] = -1;
int sec = 1;
int d = 0;
int idx = 0;
int nx = 1, ny = 1;
while(true) {
if(idx < r.length) {
if(sec-1 == r[idx].x) {
if(r[idx].c == 'L') {
if(d == 0) d = 3;
else d--;
} else {
d = (d+1)%4;
}
idx++;
}
}
nx = nx + dx[d];
ny = ny + dy[d];
if(nx < 1 || nx >= n+1 || ny < 1 || ny >= n+1 || map[nx][ny] == -1) break;
int tmp = map[nx][ny];
map[nx][ny] = -1;
snake.add(new Node(nx,ny));
if(tmp != 1) {
Node tmp2 = snake.poll();
map[tmp2.x][tmp2.y] = 0;
}
sec++;
}
System.out.println(sec);
}
static class Node{
int x;
int y;
Node(int x, int y){
this.x = x;
this.y = y;
}
}
static class Rotate{
int x;
char c;
Rotate(int x, char c){
this.x = x;
this.c = c;
}
}
}
์ฑ๊ณตโจ