🧩 문제 정보
백준 3190번 뱀
- 문제: https://www.acmicpc.net/problem/3190
- 난이도: 골드 4
- 유형: 구현, 자료구조
NewCodes의 풀이
- 스스로 풀었는가: O
- 풀이 시간: 48분
- 제출 횟수: 1번
- 선택 언어: Java
- 풀이 환경: IntelliJ IDEA CE (코드 자동완성 기능 X)
📝 풀이 과정
문제 요구 사항 정리
- 게임 시작 시 뱀 몸의 길이 1, 맨 위 맨 왼쪽(1, 1), 오른쪽
- 매 초 머리를 늘려 이동, 방향 전환(왼쪽 L, 오른쪽 D)도 존재
- 사과 유무에 따라 꼬리 유지 or 삭제
- 벽이나 몸에 부딪히면 게임 끝
문제 풀이 설계(feat. 의사 코드)
1초마다 이동하는 함수 구현하기
뱀의 머리 방향에 따라 움직이기 & time++
벽이나 몸에 부딪혔는지 확인하기
부딪혔다면 게임 끝 아니라면 고고
사과가 있다면 뱀 꼬리 유지, 없다면 자르기
방향 전환해야하는지 체크
정답으로 제출한 코드
: 실전 풀이를 보고싶으신 분은 해당 코드를 참고해주세요! 그 다음은 리팩토링한 코드를 첨부했으니 좀 더 정돈된 코드를 보고 싶으신 분은 넘겨주세요!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int[][] map;
private static int[][] apples;
private static Map<Integer, String> shifts = new HashMap<>();
private static int[] dx = {1, 0, -1, 0};
private static int[] dy = {0, 1, 0, -1};
private static int shift = 1; // 오른쪽 (왼쪽 -> 3)
// 아래 오른쪽 위 왼
private static Deque<int[]> snake = new ArrayDeque<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 입력 받기
int n = Integer.parseInt(br.readLine());
int k = Integer.parseInt(br.readLine());
map = new int[n + 1][n + 1];
apples = new int[n + 1][n + 1];
for (int i = 0; i < k; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
apples[x][y] = 2; // 사과
}
int l = Integer.parseInt(br.readLine());
for (int i = 0; i < l; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int second = Integer.parseInt(st.nextToken());
String shift = st.nextToken();
shifts.put(second, shift);
}
// System.out.println(Arrays.deepToString(map));
// System.out.println(shifts);
map[1][1] = 1;
snake.add(new int[] {1, 1});
int currentTime = 0;
boolean isGoing = true;
while (isGoing) {
currentTime++;
isGoing = move(currentTime);
}
System.out.println(currentTime);
}
public static boolean move(int currentTime) {
int[] head = snake.getFirst();
int[] nextHead = new int[] {head[0] + dx[shift], head[1] + dy[shift]};
// 뱀의 몸에 닿았거나, 벽에 닿았는지 확인
if (isSafe(nextHead)) {
snake.addFirst(nextHead);
map[nextHead[0]][nextHead[1]] = 1;
} else {
return false;
}
// 사과 확인
if (apples[nextHead[0]][nextHead[1]] == 2) {
apples[nextHead[0]][nextHead[1]] = 0;
} else {
int[] tail = snake.getLast();
map[tail[0]][tail[1]] = 0;
snake.removeLast();
}
// 방향 전환 확인
if (shifts.containsKey(currentTime)) {
if (shifts.get(currentTime).equals("L")) {
shift++;
if (shift == 4) {
shift = 0;
}
} else {
shift--;
if (shift == -1) {
shift = 3;
}
}
}
return true;
}
public static boolean isSafe(int[] nextHead) {
// 맵에서 벗어났는지 확인
if (nextHead[0] < 1 || nextHead[0] > map[0].length - 1 || nextHead[1] < 1 || nextHead[1] > map[0].length - 1) {
return false;
}
// 뱀의 몸인지 확인
if (map[nextHead[0]][nextHead[1]] == 1) {
return false;
}
return true;
}
}
/*
문제 조건
1. 게임 시작 시 뱀 몸의 길이 1, 맨 위 맨 왼쪽(1, 1), 오른쪽
2. 매 초 머리를 늘려 이동, 방향 전환(왼쪽 L, 오른쪽 D)도 존재
3. 사과 유무에 따라 꼬리 유지 or 삭제
4. 벽이나 몸에 부딪히면 게임 끝
1초마다 이동하는 함수 구현하기
뱀의 머리 방향에 따라 움직이기 & time++
벽이나 몸에 부딪혔는지 확인하기
부딪혔다면 게임 끝
아니라면 고고
사과가 있다면 뱀 꼬리 유지, 없다면 자르기
방향 전환해야하는지 체크
time 플러스한 뒤 이동 체크해야겠지?
2차원 배열 위에서 사과, 뱀의 위치, 방향 전환 표현하기
0 - 아무것도 없음
1 - 뱀
2 - 사과
0 - 아무것도 없음
1 - 왼쪽
2 - 오른쪽
한 배열에 표현하는 게 효과적일까?
왼쪽이면서 사과라면? -> 방향 정보는 따로 해두는 게 나을 듯. -> 배열, 큐가 아닌 맵으로!!
뱀을 덱으로 구현해도 되긴 하겠다!
추가 변수 -> 뱀의 머리 방향, 뱀의 머리와 꼬리 좌표
덱으로 가자!!
피드백
1. 주석 활용하길 잘한 듯. 디버깅할 때 편함.
2. 자료구조 선정에 있어 더 신중할 필요 있을 듯. (어떤 종류의 자료구조를 사용해야 할 지 뿐만 아니라 자료구조를 얼만큼 사용해야 할지도)
3. 순수 구현 문제 느낌이 느껴진다면 처음에 조건 정리하고 꼼꼼히 설계하는 데 더 신경을 기울이기
*/풀이 의도 설명
: 해당 풀이에서는 3가지 자료구조와 함께 if 문, while 문을 이용해서 문제를 해결했습니다.
3가지 자료구조에 대해 살펴보겠습니다.
int[][] map = new int[n + 1][n + 1];
int[][] apples = new int[n + 1][n + 1];
Map<Integer, String> shifts = new HashMap<>();
map을 통해서는 뱀의 위치를 표현합니다. 뱀이 위치한 각각의 좌표에는 1의 값을, 위치하지 않은 좌표는 0으로 할당하여 구별합니다. 해당 map이 쓰이는 곳은 isSafe(int[] nextHead) 메서드입니다. 뱀의 머리가 자기자신의 몸과 부딪혔는지 확인하기 위해 사용됩니다.
apples는 사과의 위치를 표현합니다. 사과가 위치한 각각의 좌표에는 2의 값을, 위치하지 않은 좌표는 0으로 할당하여 구별합니다. 해당 apples가 쓰이는 곳은 move(int[] currentTime) 메서드입니다. 뱀이 새롭게 위치한 머리 좌표에 사과가 있는지 없는지 확인하는 데 사용됩니다.
shifts는 방향 전환 정보를 저장합니다. 첫 번째 Integer는 게임 시간 초를 의미하고, 두 번째 String은 방향 전환 정보를 의미합니다. 해당 shifts가 쓰이는 곳은 move(int[] currentTime) 메서드입니다. 매 초 방향 전환을 해야 하는지 확인하는 데 사용됩니다.
위 3가지 자료구조와 함께 while, if 문을 활용하여 뱀을 구현했습니다. 특별한 알고리즘은 필요하지 않았으며, 주어진 요구사항을 기본적인 문법과 자료구조로 해결할 수 있었습니다.
리팩토링한 코드
: 좀 더 보기 편하도록 리팩토링했습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int n;
private static int[][] map;
private static int[][] apples;
private static Map<Integer, String> shifts = new HashMap<>();
// dx dy 방향: 아래 오른쪽 위 왼쪽
private static int[] dx = {1, 0, -1, 0};
private static int[] dy = {0, 1, 0, -1};
private static int shift = 1; // 오른쪽
private static Deque<int[]> snake = new ArrayDeque<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 입력 받기
n = Integer.parseInt(br.readLine());
int k = Integer.parseInt(br.readLine());
map = new int[n + 1][n + 1];
apples = new int[n + 1][n + 1];
// 사과 입력 받기
for (int i = 0; i < k; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
apples[x][y] = 2; // 사과
}
// 뱀의 방향 변환 입력 받기
int l = Integer.parseInt(br.readLine());
for (int i = 0; i < l; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int second = Integer.parseInt(st.nextToken());
String shift = st.nextToken();
shifts.put(second, shift);
}
// 뱀의 위치 초기화 (1, 1)
map[1][1] = 1;
snake.add(new int[] {1, 1});
// 뱀 이동 시작
int currentTime = 0;
boolean isGoing = true;
while (isGoing) {
currentTime++;
isGoing = move(currentTime);
}
System.out.println(currentTime);
}
public static boolean move(int currentTime) {
int[] head = snake.getFirst();
int[] nextHead = new int[] {head[0] + dx[shift], head[1] + dy[shift]};
// 뱀의 몸에 닿았거나, 벽에 닿았는지 확인 (게임 종료 확인)
if (isSafe(nextHead)) {
snake.addFirst(nextHead);
map[nextHead[0]][nextHead[1]] = 1;
} else {
return false; // 게임 종료
}
// 사과가 있는지 확인
if (apples[nextHead[0]][nextHead[1]] == 2) {
apples[nextHead[0]][nextHead[1]] = 0;
} else {
int[] tail = snake.getLast();
map[tail[0]][tail[1]] = 0;
snake.removeLast();
}
// 방향 변환 해야 하는 시각인지 확인
if (shifts.containsKey(currentTime)) {
if (shifts.get(currentTime).equals("L")) {
shift++;
if (shift == 4) {
shift = 0;
}
} else {
shift--;
if (shift == -1) {
shift = 3;
}
}
}
return true;
}
public static boolean isSafe(int[] nextHead) {
// 보드에서 벗어났는지 확인
if (nextHead[0] < 1 || nextHead[0] > n || nextHead[1] < 1 || nextHead[1] > n) {
return false;
}
// 뱀의 몸인지 확인
if (map[nextHead[0]][nextHead[1]] == 1) {
return false;
}
return true;
}
}
더 궁금한 점
- apples, map(snake 정보 담는), shifts 자료 구조 이렇게 세 개 활용하는 게 바람직한가? (2차원 배열, 2차원 배열, HashMap)
- 전역변수 이렇게 두는 게 바람직한가?
더 해야 할 것
- AI에게 리팩토링 조언 얻기
- 다른 블로그 참고하며 코드 리팩토링하기
- 객체지향, 메서드 분리, 네이밍, 자료구조 등 신경 쓰기
🎯 풀이 피드백
1. 주석 다는 습관
: 각 작은 기능마다 주석을 달아 무슨 기능인지 명시했다. 이렇게 하면 각 기능이 한 눈에 들어와서 나중에 디버깅할 때 편하다! 이 습관 정말 좋은 것 같다. 계속 가지고 가자!
사실 가장 이상적인 건 주석을 달아서 구분하는 게 아니라, 함수를 분리하는 것이다. 하지만 이는 실제 코테에서 다소 비용이 드는 일이어서 이보다는 주석을 통해 분리하는 게 경제적이다.
2. 자료구조 꼼꼼히 선정
: 처음에는 뱀의 머리, 몸통, 꼬리 위치를 2차원 배열에 저장하려 했다. 또한, 해당 배열에 사과 위치 정보도 담으려 했다. 하지만, 중간에 이상함을 느끼고 자료구조를 다시 Deque으로 선정했다. 뱀을 2차원 배열에 담으면 뱀의 머리, 꼬리 위치를 단번에 알아내기가 어렵다. 추가적인 변수 선언이 필요하게 되므로 효율적인 방법은 아니다.
알고리즘은 신중하게 선택하면서 자료구조는 왜 대충 선택했니!! 어떤 종류의 자료구조를 사용해야 할 지 뿐만 아니라, 자료구조를 대략 몇 개 정도 사용해야 할 지도 생각하자.
3. 구현 냄새가 날 때 신경 써야 할 것
: 순수 구현 문제 느낌이 느껴진다면, 처음에 조건 정리하고 꼼꼼히 설계하는 데 더 신경을 기울이자!
반응형
'Computer Science > Algorithm' 카테고리의 다른 글
| 프로그래머스 멀쩡한 사각형 - 자세한 풀이 (Java) (4) | 2024.05.29 |
|---|---|
| 백준 5430번 AC - 자세한 풀이(Java) (3) | 2024.05.24 |
| 카카오맵이 최적 경로를 결정하는 데까지 (2) | 2024.02.07 |
| 카카오맵과 티맵이 사용하는 알고리즘 - Customizable Contraction Hierarchies (2) | 2024.02.06 |
| Contraction Hierarchies - 현실에서 쓰이는 길찾기 알고리즘 (0) | 2024.02.06 |
