LETTER

 

30분내에 풀고 싶어서 중복처리 로직을 dfs 함수 안에서 직접함.(전에 풀이 방식이 기억이 안났다)

시간복잡도는 충분하다고 판단해서 이리 했음.

더 좋은 풀이-> 중복체크 (1차원 배열)을 만들어서 체크하는거.(코드 간결,시간도 더 짧음)

 

오늘풀이

import java.util.Scanner;
import java.util.*;

public class Main{
    public static int max=0;
   
    public static int sero,garo;
    public static int[][] map;
    public static boolean[][] visit;
    public static int[] dx = new int[]{0,1,0,-1};
    public static int[] dy = new int[]{1,0,-1,0};
    public static void main(String[] args){

      Scanner scan = new Scanner(System.in);
      input(scan);
      visit[0][0]=true;
      dfs(0,0,1);
      System.out.println(max);
      scan.close();
    }
    
    public static void dfs(int x,int y,int cnt)
    {
      if(max<cnt){max=cnt;}
      
      
      ArrayList<Integer> arrList = new ArrayList();
      for(int i=0;i<sero;i++)
      {
        for(int j=0;j<garo;j++)
        {
          if(visit[i][j]==true)
          {
            arrList.add(map[i][j]);
          }
        }
      }
      
      
      for(int i=0;i<4;i++)
      {
        int nx = x+dx[i];
        int ny = y+dy[i];
        
        if(nx>=0 && nx<sero && ny>=0 && ny<garo)
        {
          if(visit[nx][ny]==false)
          {
            if(!arrList.contains(map[nx][ny]))
            {
              visit[nx][ny]=true;
              dfs(nx,ny,cnt+1);
              visit[nx][ny]=false;
            }
          }
        }
      }
    }
    
    
    
    public static void input(Scanner scan)
    {
      sero = scan.nextInt();garo = scan.nextInt();
      map = new int[sero][garo];visit = new boolean[sero][garo];
      scan.nextLine();
      for(int i=0;i<sero;i++)
      {
        String x = scan.nextLine();
        for(int j=0;j<x.length();j++)
        {
          map[i][j] = x.charAt(j);
        }
      }
    }
}

class Point
{
  int x;int y;
  public Point(int x,int y)
  {
    this.x = x;this.y=y;
  }
}

 

1달전 풀이

import java.util.Scanner;


public class Main
{
  public static int sero;public static int garo;public static int max=0;
  public static int [][] a;public static boolean[][] v;public static boolean[] duplicated=new boolean[200];
  public static int[] dx = new int[]{0,1,0,-1};public static int[] dy = new int[]{1,0,-1,0};
  public static void main(String[] args)
  {
    Scanner scan = new Scanner(System.in);
    input(scan);
    v[1][1]=true;duplicated[a[1][1]]=true;
    dfs(1,1,1);
    System.out.println(max);
    scan.close();
  }
  
  public static void dfs(int x,int y,int cnt)
  {
    if(cnt>max){max=cnt;}
    for(int i=0;i<4;i++)
    {
      int cx = x+dx[i];int cy = y+dy[i];
      if(cx>=1 && cx<=sero && cy>=1 && cy<=garo)
      {
        if(!v[cx][cy])
        {
          if(!duplicated[a[cx][cy]])
          {
            v[cx][cy]=true;
            duplicated[a[cx][cy]]=true;
            dfs(cx,cy,cnt+1);
            v[cx][cy]=false;
            duplicated[a[cx][cy]]=false;
          }
        }
      }
    }
  }
  
  public static void input(Scanner scan)
  {
    sero = scan.nextInt();garo = scan.nextInt();
    a = new int[sero+1][garo+1]; v = new boolean[sero+1][garo+1];
    scan.nextLine();
    for(int i=1;i<=sero;i++)
    {
      String x = scan.nextLine();
      for(int j=0;j<x.length();j++){a[i][j+1] = x.charAt(j);}
    }
    // printArr();
  }
  
  public static void printArr()
  {
    for(int i=1;i<=sero;i++)
    {
      for(int j=1;j<=garo;j++)
      {
        System.out.print(a[i][j]+" ");
      }System.out.println();
    }
  }
  
  
}