Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- java
- 기초100제
- SELECT 절
- 백준
- 명품 자바 프로그래밍
- Python 3
- baekjoon
- 기초
- Python
- programmers
- HAVING 절
- JAVA 11
- Java11
- BOJ
- level1
- 자바
- 응용
- 개념
- 단계별로 풀어보기
- 기본
- 코딩테스트
- 파이썬
- 이론
- SQLD / SQLP
- Codeup
- pypy3
- GROUP BY 절
- 공공데이터
- 헤드퍼스트 디자인패턴
- Codeforces Round #802 (Div. 2)
Archives
- Today
- Total
Development Project
[ Baekjoon - 10/28 ] - 2314번: 이세계 게임 본문
- 소요 시간 : 30분
이세계 게임
시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 | 128 MB | 64 | 27 | 23 | 41.071% |
문제
트럭 운전사 택희는 오랜 기간 동안의 공로를 인정받아 이세계로 소환되었다. 택희가 소환된 이세계에는 천사 종족 Portableangel과 악마 종족 Legnaelbatrop이 살고 있었다. 택희는 뛰어난 알고리즘 지식을 발휘해 얼마 지나지 않아 두 종족을 모두 지배하는 이세계의 왕이 되었다.
폭군 택희는 지루해지면 이세계의 주민들을 이용해 게임을 한다. 먼저 종족과 무관하게 16명의 개체를 모아서 4×4 격자 형태로 세워 놓는다. 그 다음 각 자리에 어떤 종족이 서야 하는지를 지정해 주고, 그에 맞게 다시 서도록 명령한다. 그러면 이들은 서로 자리를 바꿔서 택희가 원하는 배치를 만들어야 한다. 자리를 바꿀 때는 상하좌우로 인접한 두 개체끼리만 바꿀 수 있으며, 한 개체가 여러 번 자리를 바꿀 수도 있다.
현재 주민들의 배치와 택희가 원하는 배치가 주어질 때, 최소 몇 번의 자리 바꿈이 필요한지 구하여라.
입력
'P' 또는 'L'을 값으로 갖는 4×4 행렬이 공백 없이 주어진다. 이는 현재 주민들의 배치를 나타내며, 'P'는 Portableangel, 'L'은 Legnaelbatrop 종족을 뜻한다.
그 다음 빈 줄이 0개 이상 주어진 뒤 택희가 원하는 배치가 같은 방식으로 주어진다. 택희에게는 최소한의 양심이 있기에 불가능한 배치는 주어지지 않는다.
출력
택희가 원하는 배치를 만들기 위해 필요한 최소 자리 바꿈 횟수를 출력한다.
예제 입력 1 복사
LLLL
PPPP
LLLP
PPLP
LPLP
PLPL
LPLP
PLPL
예제 출력 1 복사
4
- 문제를 읽고 이해하기
- 제한
- 시간 : 2초
- 메모리 : 128MB
- 문제
- 4 x 4의 지도, P와 L 두종류의 글자로 구성
- 현재맵과 원하는맵이 주어질때 최소의 이동횟수를 출력하는 문제
여기서 이동은, 대각선 방향이 아닌 인접한 한칸만이 가능하다.
- 이해
- 문제 이해에 어려움은 없었지만, 어떻게 풀어야할지 많은 고민을 했었다.
- 제한
- 문제를 익숙한 용어로 재정의와 추상화
- 이해가 어렵진 않아서 크게 그려보진 않았다. 3번에서 규칙을 얻기위해 그려봤음.
- 문제를 어떻게 해결할 것인가
- 1st 접근 - 가장자리부터 접근하기)
- 중간에 있는 아이들은 상하좌우 영역으로 바꿀 수있지만, 꼭짓점에 있는 아이들은 두방향밖에 되지 않아서,
꼭짓점(4개) -> 선쪽(8개) -> 안쪽(4개)로 접근해야한다고 생각했다. - 위 생각은 너무 단순하게 상하좌우에 본인과 다른 (해당 좌표값이 L이면 P찾고, P면 L찾아야 하므로) 좌표가 존재할것이라 생각해서 얻은 해결책이었기 떄문에, 결국 여러번 탐색하면서 찾아가야하므로 굳이 가장자리부터 접근하지 않아도 될것이라 생각했다.
- 2nd 접근 - 바꿔야하는 좌표를 L과 P에 따라 저장한뒤, L을 기준으로 가장 가까운 P를 찾아 바꾸기)
- 총 거리값이 최소가 되기 위해서는, 바꿔야하는 곳의 길이또한 짧아야한다고 생각해서, L을 기준으로 가장 최소의 길이를 갖는 좌표로 바꿔줘야한다고 생각했다.
- 위 계획을 검증
- 해당 L좌표를 기준으로 가장 짧은곳에 있는 P를 찾는 식으로 진행하면, 가능하다.
- 계획 수행 (실제코드 작성)
- Java 11
-
import java.io.*; import java.util.*; public class Main { private static class Node { boolean[][] map = new boolean[4][4]; long hash = 0; int step = 0; Node(boolean[][] map, int step) { for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { this.map[i][j] = map[i][j]; if (map[i][j]) { hash += (1 << (i * 4 + j)); } } } this.step = step; } void swap(int x, int y, int nx, int ny) { boolean temp = map[x][y]; map[x][y] = map[nx][ny]; map[nx][ny] = temp; } long getHash() { return hash; } } static Node R; static int[] dx = { -1, 1, 0, 0 }; static int[] dy = { 0, 0, -1, 1 }; static Queue<Node> q = new LinkedList<>(); static HashSet<Long> visit = new HashSet<>(); static boolean map[][] = new boolean[4][4]; static boolean result[][] = new boolean[4][4]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); for (int i = 0; i < 4; i++) { char[] temp = br.readLine().toCharArray(); for (int j = 0; j < 4; j++) { map[i][j] = temp[j] == 'L'; } } for (int i = 0; i < 4; i++) { char[] temp = br.readLine().toCharArray(); while (temp.length == 0) { temp = br.readLine().toCharArray(); } for (int j = 0; j < 4; j++) { result[i][j] = temp[j] == 'L'; } } R = new Node(result, 0); q.add(new Node(map, 0)); visit.add(q.peek().getHash()); System.out.println(bfs()); } private static int bfs() { boolean[][] temp = new boolean[4][4]; while (!q.isEmpty()) { Node now = q.poll(); if (now.getHash() == R.getHash()) { return now.step; } for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { temp[i][j] = now.map[i][j] != result[i][j]; } } for (int x = 0; x < 4; x++) { for (int y = 0; y < 4; y++) { for (int d = 0; d < 4; d++) { int nx = x + dx[d]; int ny = y + dy[d]; if (nx >= 0 && ny >= 0 && nx < 4 && ny < 4) { now.swap(x, y, nx, ny); Node next = new Node(now.map, now.step + 1); if (!visit.contains(next.getHash())) { visit.add(next.getHash()); q.add(next); } now.swap(x, y, nx, ny); } } } } } return -1; } }
-
- Python 3
-
import sys from collections import deque # sys.stdin = open("input.txt") dxy = ((-1,0),(1,0),(0,-1),(0,1)) origiMap = [sys.stdin.readline().rstrip("\n") for _ in range(4)] temp = sys.stdin.readline() wantMap = [sys.stdin.readline().rstrip("\n") for _ in range(4)] changeL = [] changeP = [] ans=0 for i in range(4): for j in range(4): if origiMap[i][j] != wantMap[i][j]: changeL.append((i, j)) if origiMap[i][j] == 'L' else changeP.append((i, j)) for i in range(len(changeL)): minDist = [9, 0] # 거리가 9이고 좌표 0로 설정 for j in range(len(changeP)): dist = abs(changeL[i][0]-changeP[j][0]) + abs(changeL[i][1]-changeP[j][1]) if minDist[0] > dist: minDist = [dist, j] ans += minDist[0] changeP.remove(changeP[minDist[1]]) print(ans)
-
- Java 11
- 결과
'CodingTest > Baekjoon' 카테고리의 다른 글
[ Baekjoon - 10/29 ] - 11399번: ATM (0) | 2022.10.29 |
---|---|
[ Baekjoon - 10/29 ] - 2606번: 바이러스 (1) | 2022.10.29 |
[ Baekjoon - 10/25 ] - 1600번: 말이 되고픈 원숭이 (1) | 2022.10.25 |
[ Baekjoon - 10/24 ] - 17218번: 비밀번호 만들기 (0) | 2022.10.24 |
[ Baekjoon - 10/24 ] - 1389번: 케빈 베이컨의 6단계 법칙 (0) | 2022.10.24 |
Comments