[백준] Two Dots
2021. 8. 23. 16:38ㆍ알고리즘 관련/그래프 탐색
Two Dots (골 4) : https://www.acmicpc.net/problem/16929
16929번: Two Dots
첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문
www.acmicpc.net
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;
}