Algorithm/Baekjoon
[JAVA][백준 1730] 판화
hampangee
2024. 6. 16. 18:51
https://www.acmicpc.net/problem/1730
오늘부터 문제는 올리지 않기로 했다!
풀이
처음에는 단순한 시뮬레이션 문제인 줄 알았는데 생각보다 복잡했다...
처음 풀이는 현재 좌표에만 무늬를 새겨넣고 다음에 갈 곳엔 새기지 않았는데 그렇게 했더니 마지막 위치에 마지막 명령을 시행하지 않는 문제가 생겼다
↓ 이전 풀이 방법 ↓
더보기
package S_1730;
// 판화
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
private static int[][] d = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private static char[] dc = {'U', 'D', 'L', 'R'};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
char[][] board = new char[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
board[i][j] = '.';
}
}
String command = br.readLine();
int r = 0;
int c = 0;
char prevCM = '.';
board: for (int i = 0; i < command.length(); i++) {
char cm = command.toCharArray()[i];
int nr = r;
int nc = c;
int cmNum = 0;
// 다음 지표
for (int j = 0; j < 4; j++) {
if (cm == dc[j]) {
nr = r + d[j][0];
nc = c + d[j][1];
// 다음 지표가 격자를 벗어난다면 명령 무시
if (nr < 0 || nc < 0 || nr >= N || nc >= N) {
continue board;
}
cmNum = j;
break;
}
}
if (i == 0) {
if (cmNum <= 1){
board[r][c] = '|';
prevCM = '|';
} else {
board[r][c] = '-';
prevCM = '-';
}
}
if (cmNum <= 1) { // 세로
if (prevCM == '|') {
board[r][c] = '|';
} else {
board[r][c] = '+';
prevCM = '|';
}
} else { // 가로
if (prevCM == '|') {
board[r][c] = '+';
prevCM = '-';
} else {
board[r][c] = '-';
}
}
r = nr;
c = nc;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
}
그래서 방법을 한턴에서 다음 가야할 곳의 위치까지 그려넣는 방법으로 푸는 것으로 바꾸었다.
다 풀고 테스트케이스는 통과하여 제출했는데 실패...
틀렸다고 나온다..
더보기
package S_1730;
// 판화
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
private static int[][] d = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private static char[] dc = {'U', 'D', 'L', 'R'};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
char[][] board = new char[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
board[i][j] = '.';
}
}
String command = br.readLine();
int r = 0;
int c = 0;
board: for (int i = 0; i < command.length(); i++) {
char cm = command.toCharArray()[i];
char shape = '.';
int nr = r;
int nc = c;
for (int j = 0; j < 4; j++) {
if (cm == dc[j]) {
nr += d[j][0];
nc += d[j][1];
// 범위를 벗어났다면 무시하고 다음 명령 수행
if (nr < 0 || nc < 0 || nr >= N || nc >= N){
continue board;
}
if (j <= 1) {
shape = '|';
} else {
shape = '-';
}
break;
}
}
// 현재 자리 확인하고 현재 그려야하는 선이 이전에 그린 선과 모양이 다를때만 +로 표시
if (board[r][c] == '.') {
board[r][c] = shape;
} else {
if (board[r][c] != shape) {
board[r][c] = '+';
}
}
board[nr][nc] = shape;
r = nr;
c = nc;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(board[i][j]);
}
System.out.println();
}
}
}
도저히 반례를 못찾겠어서 질문게시판을 뒤졌는데
새로 기록하는 부분을 그냥 바로 입력해야하는 모양을 그대로 입력하고 지나갔는데,
과거에 해당 부분을 바꿨었다면 그 기록을 토대로 교차하는지 아닌지 확인을 해줘야된다는 것이다.
그래서 코드를 아래처럼 바꾸었다
// 이전코드 : 현재 자리 확인하고 현재 그려야하는 선이 이전에 그린 선과 모양이 다를때만 +로 표시
if (board[r][c] == '.') {
board[r][c] = shape;
} else {
if (board[r][c] != shape) {
board[r][c] = '+';
}
}
board[nr][nc] = shape;
// 바뀐 코드 :
// 현재 자리 확인하고 현재 그려야하는 선이 이전에 그린 선과 모양이 다를때만 +로 표시
draw(r, c, shape);
draw(nr, nc, shape);
private static void draw(int r, int c, char shape) {
if (board[r][c] == '.') {
board[r][c] = shape;
} else {
if (board[r][c] != shape) {
board[r][c] = '+';
}
}
}
일단은 성공...!! 다들 반례를 어떻게 생각해내는 걸까..?ㅜㅜ
package S_1730;
// 판화
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
private static int[][] d = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private static char[] dc = {'U', 'D', 'L', 'R'};
private static char[][] board;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
board = new char[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
board[i][j] = '.';
}
}
String command = br.readLine();
int r = 0;
int c = 0;
board: for (int i = 0; i < command.length(); i++) {
char cm = command.toCharArray()[i];
char shape = '.';
int nr = r;
int nc = c;
for (int j = 0; j < 4; j++) {
if (cm == dc[j]) {
nr += d[j][0];
nc += d[j][1];
// 범위를 벗어났다면 무시하고 다음 명령 수행
if (nr < 0 || nc < 0 || nr >= N || nc >= N){
continue board;
}
if (j <= 1) {
shape = '|';
} else {
shape = '-';
}
break;
}
}
// 현재 자리 확인하고 현재 그려야하는 선이 이전에 그린 선과 모양이 다를때만 +로 표시
draw(r, c, shape);
draw(nr, nc, shape);
r = nr;
c = nc;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(board[i][j]);
}
System.out.println();
}
}
private static void draw(int r, int c, char shape) {
if (board[r][c] == '.') {
board[r][c] = shape;
} else {
if (board[r][c] != shape) {
board[r][c] = '+';
}
}
}
}