1 ~ 10000까지의 숫자중에 셀프 넘버가 아닌 데이터를 noSelfNumber에 집어넣고 loop를 순회하면서 selfNumber 여부를 체크하면 된다. 간단한 문제이다.

https://www.acmicpc.net/problem/4673

 

4673번: 셀프 넘버

문제 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다.  예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는

www.acmicpc.net

import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) {
        getNonSelfNumber();
    }

    public static void getNonSelfNumber() {
        List<Integer> nonSelfNumber = new ArrayList<>();

        for (int i = 1; i < 10000; i++) {
            if (!nonSelfNumber.contains(i)) {
                System.out.println(i);
            }

            nonSelfNumber.add(func(i));
        }

    }

    public static int func(int num) {
        int result = num;

        while (num != 0) {
            result += num % 10;
            num /= 10;
        }

        return result;
    }

}

최단거리 알고리즘을 공부하면서 예전해 만들었었던 미로 찾기를 다시한번 해봤다.

초년생때 이런문제가 어려웠는데 다시해보니 크게 어렵지는 않은것 같다.

DTO


package dto;

/**
 * Maze 블록의 정보를 보관하는 DTO
 * 
 * @author rokki
 *
 */
public class MazeBlock {
	private int x; // x 좌표
	private int y; // y 좌표
	private int count; // 카운트
	
	public MazeBlock(int x, int y, int count) {
		this.x = x;
		this.y = y;
		this.count = count;
	}

	public int getX() {
		return x;
	}

	public void setX(int x) {
		this.x = x;
	}

	public int getY() {
		return y;
	}

	public void setY(int y) {
		this.y = y;
	}

	public int getCount() {
		return count;
	}

	public void setCount(int count) {
		this.count = count;
	}
}

package dto;

/**
 * 거리와 맵을 저장하고 있는 클래스
 * 
 * @author rokki
 *
 */
public class ResultDto {
	private int resultCount;		// 경로 카운트
	private char[][] result;		// 최단 거리 맵
	
	public ResultDto(int resultCount, char[][] result) {
		this.resultCount = resultCount;
		this.result = result;
	}

	public int getResultCount() {
		return resultCount;
	}

	public void setResultCount(int resultCount) {
		this.resultCount = resultCount;
	}

	public char[][] getResult() {
		return result;
	}

	public void setResult(char[][] result) {
		this.result = result;
	}

}

 

Service


package service;

import java.io.IOException;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.charset.Charset;
import java.nio.file.Paths;
import java.nio.file.StandardOpenOption;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Stream;

import dto.MazeBlock;
import dto.ResultDto;
import serviceI.MazeService;

/**
 * 맵 경로를 찾는 서비스
 *
 * @author wedul
 *
 */
public class MazeServiceImpl implements MazeService {
	
	private char map[][];
	private boolean visited[][];
	private int maxX;
	private int maxY;
	private int currCount;
	private List<ResultDto> result = new ArrayList<>();

	@Override
	public void setMap(String path) throws IOException {
		List<String> mapList = readFile(path);
		this.maxY = mapList.size();
		this.maxX = mapList.get(0).length();
		this.map = new char[maxX][maxY];
		this.visited = new boolean[maxX][maxY];
		
		readFile(path).forEach((data) -> {
			for (int i = 0; i < data.length(); i++) {
				map[i][currCount] = data.charAt(i);
				visited[i][currCount] = false;
			}
			currCount++;
		});
	}

	@Override
	public void printMap() {
		for (int i = 0; i < maxY; i++) {
			for (int j = 0; j < maxX; j++) {
				System.out.print(map[j][i]);
			}
		}
	}
	
	public void printMap(char[][] paramMap) {
		for (int i = 0; i < maxY; i++) {
			for (int j = 0; j < maxX; j++) {
				System.out.print(paramMap[j][i]);
			}
		}
	}

	@Override
	public void findRoute() {
		// dfs 진행 (재귀)
		move(new MazeBlock(0, 1, 0));
	}
	
	/**
	 * map 나가기
	 * 
	 * @param dto
	 */
	private void move(MazeBlock dto) {
		int x = dto.getX();
		int y = dto.getY();
		visited[x][y] = true;
		int count = dto.getCount() + 1;
		
		// 위로 이동
		if (enableGo(new MazeBlock(x , y - 1, count))) {
			move(new MazeBlock(x, y - 1, count));
		}
		
		// 오른쪽으로 이동
		if (enableGo(new MazeBlock(x + 1, y, count))) {
			move(new MazeBlock(x + 1, y, count));
		}
		
		// 아래로 이동
		if (enableGo(new MazeBlock(x, y + 1, count))) {
			move(new MazeBlock(x, y + 1, count));
		}
		
		// 왼쪽으로 이동
		if (enableGo(new MazeBlock(x - 1, y, count))) {
			move(new MazeBlock(x - 1, y, count));
		}
		
		visited[x][y] = false;
	}
	
	/**
	 * 더 나아갈 수 있는지 확인
	 * 
	 * @param x
	 * @param y
	 * @return
	 */
	private boolean enableGo(MazeBlock dto) {
		int x = dto.getX();
		int y = dto.getY();
		
		// 경로 이탈 확인
		if (x < 0 || y < 0 || x > maxX || y > maxY) {
			return false;
		} 
		
		// 종점에 도착할 시 출려
		if (map[x][y] == 'G') {
			setResult(dto.getCount());
		}
		
		return map[x][y] == ' ' && !visited[x][y];
	}
	
	/**
	 * 경로들을 저장
	 * 
	 * @param count
	 */
	private void setResult(int count) {
		// map 복제
		char[][] cloneMap = new char[maxX][maxY];
		
		for (int i = 0 ; i < maxY; i++) {
			for (int j = 0; j < maxX; j++) {
				cloneMap[j][i] = map[j][i];
			}
		}
		
		for (int i = 0 ; i < maxY; i++) {
			for (int j = 0; j < maxX; j++) {
				if (visited[j][i]) {
					cloneMap[j][i] = '*';
				}
			}
		}
		
		result.add(new ResultDto(count, cloneMap));
	}
	
	@Override
	public void printResult() {
		ResultDto shortResult = result.get(0); // 최단경로 객체
		
		for (ResultDto dto : result) {
			System.out.println("GOAL===================" + dto.getResultCount());
			if (shortResult.getResultCount() > dto.getResultCount()) {
				shortResult = dto;
			}
		}
		
		System.out.println();
		System.out.println("short length : " + shortResult.getResultCount());
		printMap(shortResult.getResult());
	}
	
	/**
	 * nio를 사용하여 파일 읽기
	 * 
	 * @throws IOException 
	 */
	private List<String> readFile(String path) throws IOException {
		List<String> datas = new ArrayList<>();
		FileChannel fileChannel = FileChannel.open(Paths.get(path), StandardOpenOption.READ);
		 
        ByteBuffer buffer = ByteBuffer.allocate(1024);

        Charset charset = Charset.defaultCharset();
        String data = "";
 
        int byteCount;
 
        while (true) {
            byteCount = fileChannel.read(buffer);
 
            if (byteCount == -1)
                break;
 
            buffer.flip();
            data += charset.decode(buffer).toString();
            buffer.clear();
        }
 
        fileChannel.close();
        
        Stream<String> stream = Arrays.stream(data.split("\\n"));
        stream.forEach((eachData) -> {
        	datas.add(eachData);
        });
        
        return datas;
	}

}


package serviceI;

import java.io.IOException;

public interface MazeService {
	
	/**
	 * 파일에서 Map을 읽어 출력
	 * 
	 * @param path
	 * @throws IOException
	 */
	void setMap(String path) throws IOException;
	
	/**
	 * 맵 출력
	 */
	void printMap();
	
	/**
	 * 최단거리 찾기
	 */
	void findRoute();
	
	/**
	 * 최단거리 결과 출력
	 */
	void printResult();

}

package main;

public class Main {
	public static void main(String[] args) {
		MazeService service = new MazeServiceImpl();
		try {
			service.setMap("Map/maze.txt");
			service.findRoute();
			service.printResult();
		} catch (Exception e) {
			System.out.println("Fail Find Map");
		}
	}
}

 

결과


GOAL===================33 
GOAL===================31 
GOAL===================41 
GOAL===================39 
GOAL===================27 
GOAL===================25 
GOAL===================35 
GOAL===================33 
GOAL===================25 
GOAL===================23 
GOAL===================25 
GOAL===================23 

short length : 23 
################### 
********                     # 
#######*##### ## ## 
#      ******                 # 
## ##### ###*###### 
 # #  ## # #*# #  # 
   #                ******G 
###################

결국은 순회하면서 하는 DFS를 했는데 다음번에는 DP 또는 그래프 문제를 좀 많이 풀어 보고 싶다.


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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
 
        // 붕어빵 개수
        Scanner sc = new Scanner(System.in);
        List<LandDto> lands = new ArrayList<>();
 
        while (true) {
            int weight = sc.nextInt();
            int height = sc.nextInt();
 
            if (weight == 0 && height == 0) {
                break;
            }
 
            int[][] dataMatrix = new int[height][weight];
            for (int y = 0; y < height; y++) {
                for (int x = 0; x < weight; x++) {
                    dataMatrix[y][x] = sc.nextInt();
                }
            }
 
            lands.add(new LandDto(weight, height, dataMatrix, new boolean[height][weight]));
        }
 
        lands.forEach(land -> {
            calLandCount(land);
        });
 
    }
 
    private static void calLandCount(LandDto landDto) {
        int count = 0;
        for (int y = 0; y < landDto.getHeight(); y++) {
            for (int x = 0; x < landDto.getWeight(); x++) {
                if (!landDto.getVisited()[y][x]) {
                    if (landDto.getDataMatrix()[y][x] == 1) {
                        count++;
                        findLand(x, y, landDto);
                    } else {
                        landDto.getVisited()[y][x] = true;
                    }
                }
            }
        }
        System.out.println(count);
    }
 
    private static void findLand(int x, int y, LandDto landDto) {
        landDto.getVisited()[y][x] = true;
 
        if (checkIsGo(x + 1, y, landDto)) {
            findLand(x + 1, y, landDto);
        }
 
        if (checkIsGo(x + 1, y - 1, landDto)) {
            findLand(x + 1, y - 1, landDto);
        }
 
        if (checkIsGo(x, y - 1, landDto)) {
            findLand(x, y - 1, landDto);
        }
 
        if (checkIsGo(x - 1, y - 1, landDto)) {
            findLand(x - 1, y - 1, landDto);
        }
 
        if (checkIsGo(x - 1, y, landDto)) {
            findLand(x - 1, y, landDto);
        }
 
        if (checkIsGo(x - 1, y + 1, landDto)) {
            findLand(x - 1, y + 1, landDto);
        }
 
        if (checkIsGo(x, y + 1, landDto)) {
            findLand(x, y + 1, landDto);
        }
 
        if (checkIsGo(x + 1, y + 1, landDto)) {
            findLand(x + 1, y + 1, landDto);
        }
 
    }
 
    private static boolean checkIsGo(int x, int y, LandDto landDto) {
        return x >= 0 && y >= 0 && x < landDto.getWeight() && y < landDto.getHeight() && landDto.getDataMatrix()[y][x] == 1 && !landDto.getVisited()[y][x];
    }
 
    static class LandDto {
        private int weight;
        private int height;
 
        private int[][] dataMatrix;
        private boolean[][] visited;
 
        LandDto(int weight, int height, int[][] dataMatrix, boolean[][] visited) {
            this.weight = weight;
            this.height = height;
            this.dataMatrix = dataMatrix;
            this.visited = visited;
        }
 
        public int getWeight() {
            return weight;
        }
 
        public int getHeight() {
            return height;
        }
 
        public int[][] getDataMatrix() {
            return dataMatrix;
        }
 
        public boolean[][] getVisited() {
            return visited;
        }
 
    }
 
}
 
cs

자세한 소스는 git 참고

https://github.com/weduls/algorithm/tree/master/%EA%B7%B8%EB%9E%98%ED%94%84/%EC%84%AC%EC%9D%98%20%EA%B0%9C%EC%88%98

백준 알고리즘 2583번 영역구하기 문제는 DFS를 사용해서 구현해봤다. 문제지를 보자마자 읽기 싫어졌지만 읽어보면 되게 단순하게 많이 접해봤던 문제인거 같다.


https://www.acmicpc.net/problem/2583

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
import java.util.*;
 
public class Main {
 
    private static int M; // 세로
    private static int N; // 가로
    private static List<AreaWeightCntDto> areaWeightCntList = new ArrayList<>(); // 결과를 보관할 리스트
    private static List<Dot> visisted = new ArrayList<>();     // 방문여부를 체크할 리스트
    private static Set<Dot> box = new HashSet<>();             // box의 위치를 부여하는 hashset
 
    public static void main(String[] args) {
 
        Scanner in = new Scanner(System.in);
        M = in.nextInt();
        N = in.nextInt();
        int K = in.nextInt();
 
        // 공간 개수
        int areaCnt = 0;
 
        // 현재 박스의 위치 좌표를 모두 보관
        for (int i = 0; i < K; i++) {
            int x1 = in.nextInt();
            int y1 = in.nextInt();
            int x2 = in.nextInt();
            int y2 = in.nextInt();
 
            for (int tmpX = x1; tmpX < x2; tmpX++) {
                for (int tmpY = y1; tmpY < y2; tmpY++) {
                    box.add(new Dot(tmpX, tmpY));
                }
            }
        }
 
        //
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (enableGo(i, j)) {
                    ++areaCnt;
                    AreaWeightCntDto areaWeightCnt = new AreaWeightCntDto(1);
                    areaWeightCntList.add(areaWeightCnt);
                    visisted.add(new Dot(i, j));
                    getResult(i, j, areaWeightCnt);
                }
            }
        }
 
        // 결과 정렬
        areaWeightCntList.sort((o1, o2) -> {
            return o1.getCnt() > o2.getCnt() ? 1 : -1;
        });
 
        // 개수 출력
        System.out.println(areaCnt);
 
        // 출력
        areaWeightCntList.stream().forEach((e) -> {
            System.out.print(e.getCnt() + " ");
        });
 
    }
 
    /**
     * 공간들의 합을 저장할 Dto
     */
    static class AreaWeightCntDto {
        private int cnt;
 
        public AreaWeightCntDto(int cnt) {
            this.cnt = cnt;
        }
 
        public int getCnt() {
            return cnt;
        }
 
        public void setCnt(int cnt) {
            this.cnt = cnt;
        }
 
        public void increCnt() {
            ++this.cnt;
        }
    }
 
    /**
     * 공간 넓이 구하기
     *
     * @param x
     * @param y
     * @param sum
     */
    private static void getResult(int x, int y, AreaWeightCntDto sum) {
        if (enableGo(x, y + 1)) {
            visisted.add(new Dot(x, y + 1));
            sum.increCnt();
            ;
            getResult(x, y + 1, sum);
        }
 
        if (enableGo(x + 1, y)) {
            visisted.add(new Dot(x + 1, y));
            sum.increCnt();
            getResult(x + 1, y, sum);
        }
 
        if (enableGo(x, y - 1)) {
            visisted.add(new Dot(x, y - 1));
            sum.increCnt();
            getResult(x, y - 1, sum);
        }
 
        if (enableGo(x - 1, y)) {
            visisted.add(new Dot(x - 1, y));
            sum.increCnt();
            getResult(x - 1, y, sum);
        }
    }
 
    /**
     * 해당 좌표가 지나갈 수 있는 좌표인지 여부 확인
     *
     * @param x
     * @param y
     * @return
     */
    private static boolean enableGo(int x, int y) {
        // 경로 이탈 확인
        if (x < 0 || y < 0 || x >= N || y >= M) {
            return false;
        }
 
        // 이미 방문했는지, 박스가 있는 위치인지 여부 확인.
        return (!box.contains(new Dot(x, y)) && !visisted.contains(new Dot(x, y)));
    }
 
    /**
     * 좌표를 담는 Dot 객체
     */
    static class Dot {
 
        public Dot(int x, int y) {
            this.x = x;
            this.y = y;
        }
 
        private int x;
        private int y;
 
        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof Dot)) {
                return false;
            }
 
            Dot tmp = (Dot) obj;
 
            return Objects.equals(this.x, tmp.x) && Objects.equals(this.y, tmp.y);
        }
 
        @Override
        public int hashCode() {
            return Objects.hash(this.x, this.y);
        }
    }
 
}
cs




일반적으로 소수 구하는 방식으로 진행하면 시간이 너무 걸려서 에러가 발생한다. 그래서 고민하던 중에이런 생각이 났다. 모든 수는 자신의 제곱근 이상의 수로 나눠지지 않기 때문에 자신의 제곱근까지 2이상의 자연수로 나눠지는지 판단하면 된다고 생각했다. 

그 결과 된다.
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
 
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
 
        List<Integer> result = new ArrayList<>();
 
        // 순환
        for (int i = n; i <= m; i++) {
            if (isDecimal(i)) {
                result.add(i);
            }
        }
 
        // 결과 출력
        result.stream().forEach((e) -> {
            System.out.println(e);
        });
 
    }
 
    /**
     * 소수 체크
     *
     * @param num
     * @return
     */
    private static boolean isDecimal(int num) {
 
        if (1 == num) {
            return false;
        }
 
        /**
         * 자연수는 자신의 제곱근 이상의 수로 나눠지지 않는다는 조건을 이용해서, 자신의 제곱근 수 까지의 수로 나눠지는지 여부를 판단.
         */
        int sqrpData = new BigDecimal(Math.sqrt(num)).intValue();
 
        for (int i = 2; i <= sqrpData; i++) {
            if (num % i == 0) {
                return false;
            }
        }
 
        return true;
    }
 
}
cs


+ Recent posts