[JAVA] 2823번 - 유턴 싫어

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

그래프알고리즘으로 풀면된다!

그림을 그려서 어떤경우에 막다른 길이고 아닌지 파악했다.

내가 속한 위치를 기준으로 상하좌우에, '.'(길)이 최소 2개가 되어야 이동할 수 있다!

 

 

알고리즘

1. 빌딩이면 패스, 상하좌우로 길인지 탐색

2. 상하좌우 중에서 길일때마다 카운팅을 한다.

3. 카운팅이 1이하면 (=상하좌우에서 길이 하나밖에 없으니까) 막다른길이므로 1 출력

4. 그 이상이면 막다른 길이 아니므로 0 출력

 

 

그리고 처음에 BFS, DFS로 모두 시도를 했는데 정답이 안나왔다.

이 문제에서는 임의의 한 지점에서 제자리로 돌아올 수 있는지만 보면 된다.

그래서 굳이 BFS,DFS를 호출할 필요가 없을 것 같다. 

 

 

 

시간복잡도

R,C는 최대 10이다. 그래서 이중for문을 쓰더라도 O(100)이므로 1초안에 충분히 가능하다 

 

 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

 

1. 마을의 지도를 입력받는다.

2.

1. 빌딩이면 패스, 상하좌우로 길인지 탐색

2. 상하좌우 중에서 길일때마다 카운팅을 한다.

3. 카운팅이 1이하면 (=상하좌우에서 길이 하나밖에 없으니까) 막다른길이므로 1 출력

4. 그 이상이면 막다른 길이 아니므로 0 출력

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

import java.io.*;
import java.util.*;

public class Main {
   static char [][] arr;
   static int r,c;
   static int[] dx = {-1,1,0,0};
   static int[] dy = {0,0,-1,1};
   static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
              
        arr = new char[r][c];
        visited = new boolean [r][c];
        for(int i=0; i<r; i++) {
           String line = br.readLine();
           for(int j=0; j<c; j++) {
              arr[i][j] = line.charAt(j);
           }
        }
        

        for(int i=0; i<r; i++) {
           for(int j=0; j<c; j++) {
              if(arr[i][j]=='.') {
            	  int cnt=0;
            	  
            	  for(int k=0; k<4; k++) {
            		  int nx = i + dx[k];
            		  int ny = j + dy[k];
            		  
            		  if (nx >= 0 && ny >= 0 && nx < r && ny < c && arr[nx][ny] == '.') {
                          cnt++;
                      }
            	  }
            	  if(cnt<=1) {
            		  System.out.println(1);
            		  return;
            	  }
            	  
              }
           }
        }
        System.out.println(0);
    }
   
      
}