[백준] Two Dots

Two Dots (골 4) : https://www.acmicpc.net/problem/16929

16929번: Two Dots

DFS 를 이용, 주어진 좌표가 사이클을 이루는지 확인하면 된다.

  visited 배열/해쉬 테이블/set을 이용하여 이미 한번 왔다간 좌표를 재방문할 시 true, 아니면 false를 반환하면 된다.

 

C++은 visited로 set을 사용,

자바는 일반 벡터를 사용하였다. HastSet을 사용하여 했으나, HashSet 클래스의 Contains 메서드는 값을 확인할 시 객체의 Hash 값을 확인하는 작업을 거쳐서 그거 손보려면 끝도 없더라. C++의 pair가 자바에는 없는게 불편..

... 결국 hashCode 메서드랑 equals 메서드 손 봤다. hashCode 중복 문제 때문에, 일반 벡터 사용 코드는 정답으로 채점되지만 HashSet 사용 코드는 오답으로 채점되더라. 정확히 말해선, hashCode 값에 따라 정답 유무가 달라진다.

 

자바 코드

 

(x, y) 좌표를 나타내는 Location 클래스를 생성. equals 메서드를 오버라이딩해서 좌표 값이 같으면 true를 반환하도록 하였다.

 

벡터 사용 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Vector;

public class Main {
  private static char[][] map = new char[51][51];
  private static int[] dx = { 1, 0, -1, 0 };
  private static int[] dy = { 0, 1, 0, -1 };
  private static int N;
  private static int M;

  public static void main(String[] args) throws IOException {
    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer sTokenizer = new StringTokenizer(bufferedReader.readLine());

    N = Integer.parseInt(sTokenizer.nextToken());
    M = Integer.parseInt(sTokenizer.nextToken());

    // 맵 초기화
    String inputLine;
    for (int i = 0; N > i; i++) {
      inputLine = bufferedReader.readLine();
      map[i] = inputLine.toCharArray();
    }

    bufferedReader.close();

    Vector<Location> visited = new Vector<>();

    for (int x = 0; N > x; x++)
      for (int y = 0; M > y; y++) {
        Location start = new Location(x, y);
        if (DFS(start, start, visited)) {
          System.out.println("Yes");
          return;
        }
      }

    System.out.println("No");
  }

  private static boolean DFS(Location current, Location previous, Vector<Location> visited) {
    for (Location element : visited)
      if (element.equals(current))
        return true;

    visited.add(current);

    for (int loop = 0; 4 > loop; loop++) {
      int nx = current.x + dx[loop];
      int ny = current.y + dy[loop];

      if (nx < 0 || ny < 0 || nx >= N || ny >= M || (nx == previous.x && ny == previous.y))
        continue;
      if (map[nx][ny] != map[current.x][current.y])
        continue;

      Location next = new Location(nx, ny);

      if (DFS(next, current, visited))
        return true;
    }

    visited.remove(current);

    return false;
  }
}

class Location {
  public int x;
  public int y;

  Location(int x, int y) {
    this.x = x;
    this.y = y;
  }
  
  @Override
  public boolean equals(Object o) {
    if (o instanceof Location) {
      Location loc = (Location) o;
      return (this.x == loc.x && this.y == loc.y);
    }
    return false;
  }
}

 

HashSet 사용 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.HashSet;

public class Main {
  private static char[][] map = new char[51][51];
  private static int[] dx = { 1, 0, -1, 0 };
  private static int[] dy = { 0, 1, 0, -1 };
  private static int N;
  private static int M;

  public static void main(String[] args) throws IOException {
    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer sTokenizer = new StringTokenizer(bufferedReader.readLine());

    N = Integer.parseInt(sTokenizer.nextToken());
    M = Integer.parseInt(sTokenizer.nextToken());

    // 맵 초기화
    String inputLine;
    for (int i = 0; N > i; i++) {
      inputLine = bufferedReader.readLine();
      map[i] = inputLine.toCharArray();
    }

    bufferedReader.close();

    HashSet<Location> visited = new HashSet<>();

    for (int x = 0; N > x; x++)
      for (int y = 0; M > y; y++) {
        Location start = new Location(x, y);
        if (DFS(start, start, visited)) {
          System.out.println("Yes");
          return;
        }
      }

    System.out.println("No");
  }

  private static boolean DFS(Location current, Location previous, HashSet<Location> visited) {
    if (visited.contains(current))
      return true;

    visited.add(current);

    for (int loop = 0; 4 > loop; loop++) {
      int nx = current.x + dx[loop];
      int ny = current.y + dy[loop];

      if (nx < 0 || ny < 0 || nx >= N || ny >= M || (nx == previous.x && ny == previous.y))
        continue;
      if (map[nx][ny] != map[current.x][current.y])
        continue;

      Location next = new Location(nx, ny);

      if (DFS(next, current, visited))
        return true;
    }

    visited.remove(current);

    return false;
  }
}

class Location {
  public int x;
  public int y;
  private int hash;

  Location(int x, int y) {
    this.x = x;
    this.y = y;
    this.hash = x * 31 ^ (51 - x) + y * 17 ^ (51 - y); // 임의 값.
  }

  @Override
  public int hashCode() {
    return hash;
  }

  @Override
  public boolean equals(Object o) {
    if (o instanceof Location)
      return o.hashCode() == hash;
    return false;
  }
}

 

 

 

---

 

C++ 코드

#include <iostream>
#include <set>

using namespace std;

int N, M;
char map[51][51];
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

bool dfs(int x, int y, int prev_x, int prev_y, set<pair<int, int>> visited)
{
  if (visited.find({x, y}) != visited.end())
    return true;

  visited.insert({x, y});

  bool result = false;

  for (int loop = 0; 4 > loop; loop++)
  {
    int nx = x + dx[loop];
    int ny = y + dy[loop];

    if (nx < 0 || ny < 0 || nx >= N || ny >= M || (nx == prev_x && ny == prev_y))
      continue;
    if (map[nx][ny] != map[x][y])
      continue;

    result = dfs(nx, ny, x, y, visited);
    if (result)
      return result;
  }

  visited.erase({x, y});

  return result;
}

int main(void)
{
  bool result = false;
  set<pair<int, int>> visited;
  cin >> N >> M;

  for (int i = 0; N > i; i++)
    for (int j = 0; M > j; j++)
      cin >> map[i][j];

  for (int i = 0; N > i; i++)
  {
    for (int j = 0; M > j; j++)
    {
      result = dfs(i, j, i, j, visited);
      if (result)
        break;
    }
    if (result)
      break;
  }
  if (result)
    cout << "Yes" << '\n';
  else
    cout << "No" << '\n';

  return 0;
}