swea 1952 수영장
-
생각한 로직 : 1일권 - 1달권 -3달권을 선택하는 경우를 중복순열로 구하기
-
틀린이유 : 매개변수에 이미 계산 된 값을 넣은거라서 return 될때 빼줬어야되는데 안뺌
빼주거나 매개변수 안에서 계산하거나 둘중하나 택하기
정답코드
import java.util.Scanner;
public class swea1952 {
static int[] arr=new int [4];
static int[] arr2=new int[13];
static int min;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
int t = scan.nextInt();
min=0;
for (int o = 1; o <= t; o++) {
for(int i=0;i<4;i++) {
arr[i]=scan.nextInt(); //이용권 가격
}
for(int i=0;i<12;i++) {
arr2[i+1]=scan.nextInt();
}
min=arr[3];
dfs(1,0);
System.out.println("#"+o+" "+(min));
}
}
public static void dfs(int month,int result) {
if(result>min)return;
if(month>=13) {
if(min>result) {
min=result;
}
return;
}
for(int i=0;i<3;i++) { //1일권 1달권 3달권 경우의 수 다 시도해보기
if(arr2[month]==0) dfs(month+1,result);
if(i==0) {//1일
result+=arr[i]*arr2[month];
dfs(month+1,result);
result-=arr[i]*arr2[month];
}
else if(i==1) {//1달권
result+=arr[i];
dfs(month+1,result);
result-=arr[i];
}
else if(i==2) {//3달권
result+=arr[i];
dfs(month+3,result);
result-=arr[i];
}
}
}
}
swea 1953 탈주범 검거
- 생각한 로직 : 상하좌우 움직일 수있는지 없느지를 담는 클래스 만든다 -> 현재위치에서 블럭에 해당하는 상하좌우 true false를 찾는다.(다음칸이 빈칸이여도 안됨 격자밖이여도안됨 )-> 해당하는 방향을 bfs한다. 해당하는 depth가 될때까지 반복한다. (visited 체크한다.)
- 틀린 이유 : 다음 배관의 방향도 체크해야함, depth가 L보다 작을때만 큐에 넣어줘야함
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class pos {
int x;
int y;
int dep;
pos(int x, int y, int dep) {
this.x = x;
this.y = y;
this.dep = dep;
}
}
public class swea1953 {
static int N,M,R,C,L;
static int[][] arr;
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, -1, 1 };
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
int t = scan.nextInt();
for (int o = 1; o <= t; o++) {
N=scan.nextInt();
M=scan.nextInt();
//맨홀 (시작점)
R=scan.nextInt();
C=scan.nextInt();
//소요시간 (depth)
L=scan.nextInt();
arr=new int[N][M];
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
arr[i][j]=scan.nextInt(); //배관 정보
}
}
int ans=bfs(R,C);
System.out.println("#"+o+" "+ans);
}
}
public static int bfs(int R, int C) {
int cnt=1;
boolean visited[][]=new boolean[N][M];
Queue<pos> q=new LinkedList<>();
q.offer(new pos(R,C,1));
visited[R][C]=true;
while(!q.isEmpty()) {
pos cur=q.poll();
boolean[] dir=move(arr[cur.x][cur.y]);
for(int i=0;i<4;i++) {
if(!dir[i]) continue;
int nx=cur.x+dx[i];
int ny=cur.y+dy[i];
if(nx>=0&&ny>=0&&nx<N&&ny<M&&!visited[nx][ny]&&cur.dep<L&&arr[nx][ny]>0) {
boolean[] dir2=move(arr[nx][ny]);
boolean flag=false;
if(i==0&&dir2[1]) {
flag=true;
}
else if(i==1&&dir2[0]) {
flag=true;
}
else if(i==2&&dir2[3]) {
flag=true;
}
else if(i==3&&dir2[2]) {
flag=true;
}
if(flag) {
visited[nx][ny]=true;
q.offer(new pos(nx,ny,cur.dep+1));
cnt++;
}
}
}
}
return cnt;
}
public static boolean[] move(int type) {
boolean[] arr = null;
if(type==1) {
arr= new boolean[] {true,true,true,true};
}
else if(type==2) {
arr= new boolean[] {true,true,false,false};
}
else if(type==3) {
arr= new boolean[] {false,false,true,true};
}
else if(type==4) {
arr= new boolean[] {true,false,false,true};
}
else if(type==5) {
arr= new boolean[] {false,true,false,true};
}
else if(type==6) {
arr= new boolean[] {false,true,true,false};
}
else if(type==7) {
arr= new boolean[] {true,false,true,false};
}
return arr;
}
}swea4008 숫자 만들기
- 생각한 로직 : dfs 중복조합을 visited체크하며 해준
import java.util.Scanner;
public class swea4008 {
static int N,max,min;
static int[] arr,arr2;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
int t = scan.nextInt();
for (int o = 1; o <= t; o++) {
max=Integer.MIN_VALUE;
min=Integer.MAX_VALUE;
N=scan.nextInt();
arr=new int[4];
arr2=new int[N];
for(int i=0;i<4;i++) {
arr[i]=scan.nextInt();
}
for(int j=0;j<N;j++) {
arr2[j]=scan.nextInt();
}
dfs(1,arr2[0]);
System.out.println("#"+o+" "+(max-min));
}
}
public static int cal(int a,int b,int c) {
int ans=0;
if(b==0) {
ans= a+c;
}
else if(b==1) {
ans= a-c;
}
else if(b==2) {
ans= a*c;
}
else if(b==3) {
ans=a/c;
}
return ans;
}
public static void dfs(int depth,int result) {
if(depth==N) {
if(max<result) {
max=result;
}
if(min>result) {
min=result;
}
return;
}
for(int i=0;i<4;i++) {
if(arr[i]>0) {
arr[i]--;
int r=cal(result,i,arr2[depth]);
dfs(depth+1,r);
arr[i]++;
}
}
}
}swea 7793 오 나의 여신님
틀린이유
- visited 재귀 돌아올때 초기화
1번 미스를 고치고 로직에 아무문제도 없는것같은데 테케는 두개는 다맞았지만 제출하면 계속 절반만 맞다고 떠서 print문을 바꿔보거나 bufferedreader로 읽어보거나 솔루션 보고 거의 똑같이 바꿔도 계속 틀렸다고 떠서 이틀 동안 엄청 답답해하다가 29트만에 틀린 이유를 찾아냈다.
- 큐의 사이즈 만큼 반복문을 돌때 for문 안에 q.size()이렇게 해버리면 for문을 돌면서 큐의 사이즈가 변하기때문에 오답이 났던것ㅠㅠ...
오답코드 (5/10)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Solution {
static int N, M;
static char[][] arr;
static Queue<pos3> soo,devil ;
static int[] dx = { 1, -1, 0, 0 };
static int[] dy = { 0, 0, 1, -1 };
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
for (int o = 1; o <= t; o++) {
soo= new LinkedList<>();
devil = new LinkedList<>();
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new char[N][M];
for (int i = 0; i < N; i++) {
arr[i] = br.readLine().toCharArray();
for (int j = 0; j < M; j++) {
if (arr[i][j] == 'S') { // 수연이 초기 위치
soo.offer(new pos3(i, j));
} else if (arr[i][j] == '*') { // 악마들 초기 위치
devil.offer(new pos3(i, j));
}
}
}
// 수연이의 위치 S 여신의 위치 D 돌 X 악마 *
int min = dfs();
System.out.println("#" + o + " " + (min == 0 ? "GAME OVER" : min));
}
}
static void print() {
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
System.out.print(arr[i][j]+" ");
}
System.out.println();
}
System.out.println("------------");
}
public static int dfs() {
int cnt = 0;
while (!soo.isEmpty()) {
// 악마 이동
for (int a = 0; a < devil.size(); a++) {
pos3 cur = devil.poll();
for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < M&&(arr[nx][ny] == '.' || arr[nx][ny] == 'S') ) {
devil.offer(new pos3(nx, ny));
arr[nx][ny] = '*';
}
}
}
// 수연이 이동
for (int a = 0; a < soo.size(); a++) {
pos3 p = soo.poll();
for (int i = 0; i < 4; i++) {
int sx = p.x + dx[i];
int sy = p.y + dy[i];
if (sx >= 0 && sy >= 0 && sx < N && sy < M) { // 악마가 방문하지않은 지역이여야함
if (arr[sx][sy] == '.') {
soo.offer(new pos3(sx, sy));
arr[sx][sy] = 'S';
}
else if (arr[sx][sy] == 'D') {
return cnt+1;
}
}
}
}
cnt++;
//print();
}
return 0;
}
static class pos3 {
int x;
int y;
pos3(int x, int y) {
this.x = x;
this.y = y;
}
}
}정답코드
package algo;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class swea7793 {
static int N, M;
static char[][] arr;
static Queue<pos3> soo,devil ;
static int[] dx = { 1, -1, 0, 0 };
static int[] dy = { 0, 0, 1, -1 };
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
for (int o = 1; o <= t; o++) {
soo= new LinkedList<>();
devil = new LinkedList<>();
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new char[N][M];
for (int i = 0; i < N; i++) {
arr[i] = br.readLine().toCharArray();
for (int j = 0; j < M; j++) {
if (arr[i][j] == 'S') { // 수연이 초기 위치
soo.add(new pos3(i, j));
} else if (arr[i][j] == '*') { // 악마들 초기 위치
devil.add(new pos3(i, j));
}
}
}
// 수연이의 위치 S 여신의 위치 D 돌 X 악마 *
int min = dfs();
System.out.println("#" + o + " " + (min == 0 ? "GAME OVER" : min));
}
}
static void print() {
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
System.out.print(arr[i][j]+" ");
}
System.out.println();
}
System.out.println("------------");
}
public static int dfs() {
int cnt = 0;
while (!soo.isEmpty()) {
// 악마 이동
int size= devil.size();
for (int a = 0; a <size; a++) {
pos3 cur = devil.poll();
for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < M&&(arr[nx][ny] == '.' || arr[nx][ny] == 'S') ) {
devil.offer(new pos3(nx, ny));
arr[nx][ny] = '*';
}
}
}
// 수연이 이동
int size2=soo.size();
for (int a = 0; a <size2 ; a++) {
pos3 p = soo.poll();
for (int i = 0; i < 4; i++) {
int sx = p.x + dx[i];
int sy = p.y + dy[i];
if (sx >= 0 && sy >= 0 && sx < N && sy < M) { // 악마가 방문하지않은 지역이여야함
if (arr[sx][sy] == '.') {
soo.offer(new pos3(sx, sy));
arr[sx][sy] = 'S';
}
else if (arr[sx][sy] == 'D') {
return cnt+1;
}
}
}
}
cnt++;
//print();
}
return 0;
}
static class pos3 {
int x;
int y;
pos3(int x, int y) {
this.x = x;
this.y = y;
}
}
}
남기고 싶은 개발자입니다 :>