@DFS / 35m
쉬운 문제였다.
그런데 마지막 사각형이 만들어질 때 예외처리를 해주지 않으면 직사각형이 아닌 다른 모양으로 만들어져서, 테케가 틀리게 나온다.
그 부분만 신경쓰면 끝나는 문제.
문제 링크
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu
구현 방법
# 문제의 화살표 방향과 반대로 구현했을 때의 풀이방법이다. (별 의도는 없고 하다보니..)
1. 사각형에서 제일 위에 있는 점에서 시작했다.
이중 for문을 돌면서 (이때 세로는 0 <= i < N - 1, 가로는 1 <= j <= N - 1 로 했다.)
시작할 점을 찾는다.
2. 일반적인 사방탐색과 다르게, 대각선 방향으로 움직이므로
첫 점에서 왼쪽 아래, 두번째 점에서는 오른쪽 아래, 세번째 점에서는 오른쪽 위, 네번째 점에서는 왼쪽 위로 움직인다.
그래서 int[] dx = {1, 1, -1, -1}, dy = {-1, 1, 1, -1}; 이렇게 배열 값을 설정했다.
구현 포인트
1. 진행 방향은 지금 방향을 유지하느냐, 다음 방향으로 바꾸느냐 두 가지이다.
그래서 for문을 두번 돌리고(i는 0또는 1) , 방향에 대해서는 (지금방향 + i) % 4 이렇게 해주면, 직진 또는 방향을 꺾어서 dfs가 돌게 된다.
2. 문제는, 1번 처럼만 처리해주면 테케를 돌렸을때 값이 답보다 크게 나온다.
이유는 그냥 for문을 돌리면 선이 4번에서 끝나는게 아니라 더 그어지는 경우가 생기기 때문이었다.
그래서 만약 지금 4번째 선을 긋고 있는 중이라면, 이때는 방향을 꺾지 않게끔 if문을 하나 넣어줬더니 정상적으로 돌아갔다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Solution {
private static int N, map[][], maxCount;
private static int[] dx = {1, 1, -1, -1}, dy = {-1, 1, 1, -1};
private static boolean[] visit;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
maxCount = -1;
visit = new boolean[101];
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++)
map[i][j] = Integer.parseInt(st.nextToken());
}
findStart();
sb.append("#" + t + " " + maxCount + "\n");
}
System.out.println(sb);
}
private static void findStart() {
for (int i = 0; i < N - 1; i++) {
for (int j = 1; j < N - 1; j++) {
visit[map[i][j]] = true;
dfs(i, j, 0, i, j, 1);
visit[map[i][j]] = false;
}
}
}
private static void dfs(int x, int y, int d, int sx, int sy, int count) {
for (int i = 0; i < 2; i++) {
if (d + i == 4) return;
int dir = (d + i) % 4;
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue; //visit은 도착점체크한 후에 체크하기
if (sx == nx && sy == ny) {
if (maxCount < count) maxCount = count;
return;
}
if (visit[map[nx][ny]]) continue;
visit[map[nx][ny]] = true;
dfs(nx, ny, dir, sx, sy, count + 1);
visit[map[nx][ny]] = false;
}
}
}
끝!
'algorithm > SW Expert Academy' 카테고리의 다른 글
[SWEA] 8382.방향 전환 (java) / 시뮬레이션 (0) | 2020.03.05 |
---|---|
[SWEA] 5650.핀볼 게임 / 시뮬레이션 (0) | 2020.01.27 |
[SWEA] 4008.숫자 만들기 / Next-Permutation (0) | 2020.01.26 |
[SWEA] 1953.탈주범 검거 (java) / BFS (0) | 2020.01.26 |
[SWEA] 2117.홈 방범 서비스 (java) / BFS 또는 List 활용 (0) | 2020.01.26 |
댓글