[D3] 격자판 칠하기 - 14413
성능 요약
메모리: 36,684 KB, 시간: 181 ms, 코드길이: 2,264 Bytes
제출 일자
2023-10-22 20:00
출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do
생각 했던 풀이
1. for문을 돌려서 현재 위치 인덱스의 값이 '?'가 아니라면 BFS 함수를 통해서 격차를 채워준다.
2. 만약 채우는 도중 배열의 cur값과 next값이 같으면 invalid한 값이므로 return false
3. false를 리턴하지 않는다면 valid한 값
import java.util.*;
import java.io.*;
class Solution
{
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
char[][] map;
int T = sc.nextInt();
for(int tc = 1; tc <= T; tc++)
{
String result = "possible";
int a = sc.nextInt();
int b = sc.nextInt();
map = new char[a][b];
for(int i = 0; i < a; i++){
String line = sc.next();
for(int j = 0; j < b; j++){
map[i][j] = line.charAt(j);
}
}
loop : for(int i = 0; i < a; i++){
for(int j = 0; j < b; j++){
if(map[i][j] != '?'){
if(!solution(map,i,j)){
result = "impossible";
break loop;
}
}
}
}
System.out.printf("#%d %s\n",tc,result);
}
}
private static boolean solution(char[][] map, int x, int y){
int[] dirX = {1,-1,0,0};
int[] dirY = {0,0,-1,1};
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] {x,y});
while(!queue.isEmpty()){
int[] cur = queue.poll();
int curX = cur[0];
int curY = cur[1];
for(int i =0; i < 4; i++){
int nextX = curX + dirX[i];
int nextY = curY + dirY[i];
// 범위보다 크거나 이미 문자가 존재할 때
if((nextX < 0 || nextY < 0 || nextX >= map.length || nextY >= map[0].length)){
continue;
}
if(map[nextX][nextY] == map[curX][curY]){
return false;
}
if(map[nextX][nextY] != '?'){
continue;
}
if(map[curX][curY] == '#'){
map[nextX][nextY] = '.';
}else{
map[nextX][nextY] = '#';
}
queue.offer(new int[]{nextX,nextY});
}
}
return true;
}
}
더 쉬운 풀이
1. 격자판의 성질을 이용한다.
2. 두가지 경우의 수를 놓고 생각한다. 0,2,4....등의 짝수번째 위치와 1,3,5...등 홀수번째 위치가 같지 않다면 가능함
3. 홀수번째 인덱스의 value 짝수번째 인덱스의 value가 같다면? invalid한 경우임
import java.util.*;
import java.io.*;
class Solution
{
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
char[][] map;
int T = sc.nextInt();
for(int tc = 1; tc <= T; tc++)
{
String result = "impossible";
int a = sc.nextInt();
int b = sc.nextInt();
map = new char[a][b];
for(int i = 0; i < a; i++){
String line = sc.next();
for(int j = 0; j < b; j++){
map[i][j] = line.charAt(j);
}
}
if(check(map,'#','.') || check(map,'.','#')) {
result = "possible";
}
System.out.printf("#%d %s\n",tc,result);
}
}
private static boolean check(char[][] map,char a,char b){
for(int i =0; i < map.length; i++){
for(int j = 0; j < map[0].length; j++){
if((i + j) % 2 == 0 && map[i][j] == a){
return false;
}else if((i + j) % 2 == 1 && map[i][j] == b){
return false;
}
}
}
return true;
}
}
처음부터 너무 어렵게 생각하지말기
'알고리즘 - SWEA > D3' 카테고리의 다른 글
[SW expert Academy] SWEA 14178번 1차원 정원 자바(Java) (1) | 2023.10.22 |
---|---|
[SW expert Academy] SWEA 14361번 숫자가 같은 배수 자바(Java) (0) | 2023.10.22 |
[SW expert Academy] SWEA 14555번 공과 잡초 자바(Java) (0) | 2023.10.22 |
[SW expert Academy] SWEA 14692번 통나무 자르기 자바(Java) (1) | 2023.10.21 |
[SW expert Academy] SWEA 15230번 알파벳 공부 자바(Java) (0) | 2023.10.21 |