글 읽기 - 맞은 코드와 틀린 코드의 로직 차이를 모르겠습니다.

(追記) (追記ここまで)

맞은 코드와 틀린 코드의 로직 차이를 모르겠습니다.

17489번 - 보물 찾기

ckwjdgur12 9달 전 0

findTreasure이라는 함수를 만들었습니다.

이때 찾아야 할 메시지의 끝까지 왔을때 처리하는 로직을 for문 안에 하느냐, 밖에 하느냐에 따라 차이가 나는 것 같습니다.

그런데 무슨 차이인지 한참을 고민해도 모르겠습니다. 반례가 있을까요?

맞았을때와 틀렸을때의 함수와, 호출하는 부분을 주석으로 표시해 두었습니다.

import java.io.*;
import java.util.StringTokenizer;
public class BOJ_17489_보물찾기 {
 static int N, M, L;
 static int maxK = -1;
 static int ansX = -1;
 static int ansY = -1;
 static char[][] grid;
 static boolean[][] v;
 static String msg;
 static int[] dx = {-1, 0, 1, 0};
 static int[] dy = {0, 1, 0, -1};
 //틀렸습니다 받은 함수
 private static boolean findTreasure(int x, int y, int msgPos, int k) {
 for (int i = 0; i < 4; i++) {
 int nx = x + dx[i];
 int ny = y + dy[i];
 if (!inRange(nx, ny)) continue;
 if (grid[nx][ny] != msg.charAt(msgPos)) continue;
 if (v[nx][ny]){
 maxK = -1;
 return false;
 }
 v[x][y] = true;
 if (msgPos == L-1){
 if (k > maxK){
 maxK = k;
 ansX = nx;
 ansY = ny;
 }
 if(!findTreasure(nx, ny, 0, k + 1)) return false;
 } else{
 if(!findTreasure(nx, ny, msgPos + 1, k)) return false;
 }
 v[nx][ny] = false;
 }
 return true;
 }
 // 맞았습니다 받은 함수
 private static boolean findTreasure(int x, int y, int msgPos, int k) {
 v[x][y] = true;
 if (msgPos == L){
 if (k > maxK){
 maxK = k;
 ansX = x;
 ansY = y;
 }
 msgPos = 0;
 }
 for (int i = 0; i < 4; i++) {
 int nx = x + dx[i];
 int ny = y + dy[i];
 if (!inRange(nx, ny)) continue;
 if (grid[nx][ny] != msg.charAt(msgPos)) continue;
 if (v[nx][ny]){
 maxK = -1;
 return false;
 }
 findTreasure(nx, ny, msgPos + 1, msgPos == 0 ? k + 1 : k);
 v[nx][ny] = false;
 }
 return true;
 }
 public static boolean inRange(int x, int y) {
 return (0 <= x && x < N && 0 <= y && y < M);
 }
 public static void main(String[] args) throws IOException {
 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 StringBuilder sb = new StringBuilder();
 StringTokenizer st = null;
 st = new StringTokenizer(br.readLine());
 N = Integer.parseInt(st.nextToken());
 M = Integer.parseInt(st.nextToken());
 L = Integer.parseInt(st.nextToken());
 grid = new char[N][M];
 v = new boolean[N][M];
 msg = br.readLine();
 for (int i = 0; i < N; i++) {
 String input = br.readLine();
 for (int j = 0; j < M; j++) {
 grid[i][j] = input.charAt(j);
 }
 }
 // 맞았습니다 호출
 findTreasure(0, 0, 1 % L, 1);
 
 // 틀렸습니다 호출
 findTreasure(0, 0, 1, 1);
 
 sb.append(maxK).append('\n');
 if (maxK != -1){
 sb.append(ansX + 1).append(" ").append(ansY + 1);
 }
 bw.write(sb.toString());
 bw.flush();
 }
}

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC