๐ก Info
๋ด์ฉ
NxN ํฌ๊ธฐ์ ๋ณต๋๊ฐ ์๋ค. ๋ณต๋๋ 1x1 ํฌ๊ธฐ์ ์นธ์ผ๋ก ๋๋์ด์ง๋ฉฐ, ํน์ ํ ์์น์๋ ์ ์๋, ํ์, ํน์ ์ฅ์ ๋ฌผ์ด ์์นํ ์ ์๋ค. ํ์ฌ ๋ช ๋ช ์ ํ์๋ค์ ์์ ์๊ฐ์ ๋ชฐ๋ ๋ณต๋๋ก ๋น ์ ธ๋์๋๋ฐ, ๋ณต๋๋ก ๋น ์ ธ๋์จ ํ์๋ค์ ์ ์๋์ ๊ฐ์์ ๋คํค์ง ์๋ ๊ฒ์ด ๋ชฉํ์ด๋ค.
๊ฐ ์ ์๋๋ค์ ์์ ์ ์์น์์ ์, ํ, ์ข, ์ฐ 4๊ฐ์ง ๋ฐฉํฅ์ผ๋ก ๊ฐ์๋ฅผ ์งํํ๋ค. ๋จ, ๋ณต๋์ ์ฅ์ ๋ฌผ์ด ์์นํ ๊ฒฝ์ฐ, ์ ์๋์ ์ฅ์ ๋ฌผ ๋คํธ์ ์จ์ด ์๋ ํ์๋ค์ ๋ณผ ์ ์๋ค. ๋ํ ์ ์๋์ ์, ํ, ์ข, ์ฐ 4๊ฐ์ง ๋ฐฉํฅ์ ๋ํ์ฌ, ์๋ฌด๋ฆฌ ๋ฉ๋ฆฌ ์๋๋ผ๋ ์ฅ์ ๋ฌผ๋ก ๋งํ๊ธฐ ์ ๊น์ง์ ํ์๋ค์ ๋ชจ๋ ๋ณผ ์ ์๋ค๊ณ ๊ฐ์ ํ์.
๋ค์๊ณผ ๊ฐ์ด 3x3 ํฌ๊ธฐ์ ๋ณต๋์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง ์ํฉ์ ํ์ธํด๋ณด์. ๋ณธ ๋ฌธ์ ์์ ์์น ๊ฐ์ ๋ํ๋ผ ๋๋ (ํ,์ด)์ ํํ๋ก ํํํ๋ค. ์ ์๋์ด ์กด์ฌํ๋ ์นธ์ T, ํ์์ด ์กด์ฌํ๋ ์นธ์ S, ์ฅ์ ๋ฌผ์ด ์กด์ฌํ๋ ์นธ์ O๋ก ํ์ํ์๋ค. ์๋ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด (3,1)์ ์์น์๋ ์ ์๋์ด ์กด์ฌํ๋ฉฐ (1,1), (2,1), (3,3)์ ์์น์๋ ํ์์ด ์กด์ฌํ๋ค. ๊ทธ๋ฆฌ๊ณ (1,2), (2,2), (3,2)์ ์์น์๋ ์ฅ์ ๋ฌผ์ด ์กด์ฌํ๋ค.
์ด ๋ (3,3)์ ์์น์ ์กด์ฌํ๋ ํ์์ ์ฅ์ ๋ฌผ ๋คํธ์ ์จ์ด ์๊ธฐ ๋๋ฌธ์ ๊ฐ์๋ฅผ ํผํ ์ ์๋ค. ํ์ง๋ง (1,1)๊ณผ (2,1)์ ์์น์ ์กด์ฌํ๋ ํ์์ ์ ์๋์๊ฒ ๋คํค๊ฒ ๋๋ค.
ํ์๋ค์ ๋ณต๋์ ๋น ์นธ ์ค์์ ์ฅ์ ๋ฌผ์ ์ค์นํ ์์น๋ฅผ ๊ณจ๋ผ, ์ ํํ 3๊ฐ์ ์ฅ์ ๋ฌผ์ ์ค์นํด์ผ ํ๋ค. ๊ฒฐ๊ณผ์ ์ผ๋ก 3๊ฐ์ ์ฅ์ ๋ฌผ์ ์ค์นํ์ฌ ๋ชจ๋ ํ์๋ค์ ๊ฐ์๋ก๋ถํฐ ํผํ๋๋ก ํ ์ ์๋์ง ๊ณ์ฐํ๊ณ ์ ํ๋ค. NxN ํฌ๊ธฐ์ ๋ณต๋์์ ํ์ ๋ฐ ์ ์๋์ ์์น ์ ๋ณด๊ฐ ์ฃผ์ด์ก์ ๋, ์ฅ์ ๋ฌผ์ ์ ํํ 3๊ฐ ์ค์นํ์ฌ ๋ชจ๋ ํ์๋ค์ด ์ ์๋๋ค์ ๊ฐ์๋ฅผ ํผํ๋๋ก ํ ์ ์๋์ง ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์๋ฅผ ๋ค์ด N=5์ผ ๋, ๋ค์๊ณผ ๊ฐ์ด ์ ์๋ ๋ฐ ํ์์ ์์น ์ ๋ณด๊ฐ ์ฃผ์ด์ก๋ค๊ณ ๊ฐ์ ํ์.
์ด ๋ ๋ค์๊ณผ ๊ฐ์ด 3๊ฐ์ ์ฅ์ ๋ฌผ์ ์ค์นํ๋ฉด, ๋ชจ๋ ํ์๋ค์ ์ ์๋์ ๊ฐ์๋ก๋ถํฐ ํผํ๋๋ก ๋ง๋ค ์ ์๋ค.
๐ฅ์ ๋ ฅ ์กฐ๊ฑด
//์1
5
X S X X T
T X S X X
X X X X X
X T X X X
X X T X X
//์2
4
S S S T
X X X X
X X X X
T T T X
๐ค์ถ๋ ฅ ์กฐ๊ฑด
//์1
YES
//์2
NO
์ค์ ํ์ด ์๊ฐ : 50๋ถ
์ ๋ ฅ
๊ณ์ฐ
์ถ๋ ฅ
๋ณ๋ ๋ฉ์๋
import java.util.*;
public class Main {
static int N;
static int[][] arr;
static int[] dx = {-1, 1, 0 ,0};
static int[] dy = {0, 0, -1, 1};
static boolean result;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
sc.nextLine();
arr = new int[N][N];
for(int i=0; i<N; i++){
String map = sc.nextLine();
for(int j=0; j<N; j++){
arr[i][j] = map.charAt(0) - '0';
}
}
result = bfs();
if(result == true){
System.out.println("YES");
} else {
System.out.println("NO");
}
}
public static boolean bfs(){
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (arr[i][j] == 2) {
queue.offer(new int[]{i, j});
}
}
}
while(!queue.isEmpty()){
int[] now = queue.poll();
int x = now[0];
int y = now[1];
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >=N || ny >=N){
continue;
}
arr[nx][ny] = 2;
queue.offer(new int[]{nx,ny});
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (arr[i][j] == 0) {
return false;
}
}
}
return true;
}
}
map.charAt(0) - '0'
-> map.charAt(j)
๋ก ๋ณ๊ฒฝ...
public static boolean check() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (arr[i][j] == 'T') {
for (int k = 0; k < 4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
while (nx >= 0 && nx < N && ny >= 0 && ny < N) {
if (arr[nx][ny] == 'S') return true;
if (arr[nx][ny] == 'O') return false;
nx += dx[k];
ny += dy[k];
}
}
}
}
}
return true;
}
์ค์ ํ์ด ์๊ฐ : 1์๊ฐ 48๋ถ(์ค์ ํ์ด ์๊ฐ ํฌํจ)
์ ๋ ฅ
๊ณ์ฐ
์ถ๋ ฅ
๋ณ๋ ๋ฉ์๋
BFS
check
import java.util.*;
public class Main {
static int N;
static char[][] arr;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static boolean foundSolution;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
sc.nextLine();
arr = new char[N][N];
for (int i = 0; i < N; i++) {
String map = sc.nextLine();
for (int j = 0; j < N; j++) {
arr[i][j] = map.charAt(j * 2); // ๊ณต๋ฐฑ
}
}
foundSolution = false;
dfs(0);
if (foundSolution) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
public static void dfs(int count) {
if (count == 3) { // ์ฅ์ ๋ฌผ 3๊ฐ ์ค์น
if (check()) {
foundSolution = true;
}
return;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (arr[i][j] == 'X') {
arr[i][j] = 'O';
dfs(count + 1);
if (foundSolution) return;
arr[i][j] = 'X';
}
}
}
}
// ๊ฐ์๋ฅผ ํผํ ์ ์๋์ง ํ์ธํ๋ ๋ฉ์๋
public static boolean check() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (arr[i][j] == 'T') {
for (int k = 0; k < 4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
while (nx >= 0 && nx < N && ny >= 0 && ny < N) {
if (arr[nx][ny] == 'S') {
return false; // ํ์ ๋ฐ๊ฒฌ ์ false
}
if (arr[nx][ny] == 'O') {
break; // ์ฅ์ ๋ฌผ ๋ฐ๊ฒฌ ์ ์ค์ง
}
nx += dx[k];
ny += dy[k];
}
}
}
}
}
return true; // ๋ชจ๋ ์ ์๋์ด ํ์์ ๋ฐ๊ฒฌํ์ง ๋ชปํ๋ ๊ฒฝ์ฐ์ ํด๋น
}
}