Strong Root

보글게임(BOGGLE) 정답 코드 및 해설

뿌리튼튼 CS/Algorithm2014. 11. 22. 17:45

문제를 보시려면 여기를 클릭


이하는 풀이입니다.


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
#include <iostream>
#include <string>
#include <string.h>
#pragma warning(disable:4996)
 
using namespace std;
 
char board[5][5];    // 입력받은 게임판
int cache[5][5][10];    // 결과값들을 저장한다. memset으로 -1로 초기화 후 사용. 1:성공, 0:실패
string word;    // 찾아야할 단어
 
/*
핵심 재귀 함수.
(y,x) 포인트에서 word Index에 해당하는 단어를 찾는다.
성공시 1 리턴, 실패시 0 리턴.
리턴 값들을 캐시에도 저장한다.
*/
int canFindWord(int y, int x, int wordIndex) {
    /* 범위를 벗어날 경우 */
    if ((x > 4) || (x < 0) || (y > 4) || (y < 0)) {
        return 0;
    }
 
    int& ret = cache[y][x][wordIndex];    // 이 코드를 통해 ret == cache[y][x][wordIndex] 가 된다.
 
    /* 캐시에 이미 결과가 계산되어 있으면, 추가로 계산하지 않고 그 값을 그대로 리턴(활용)한다. */
    if (ret != -1) {
        return ret;
    }
 
    /* 여기부터 이 함수 끝까지가 실제 핵심 계산부 */
 
    /*
    word Index에 해당하는 단어가, 현재 게임판에서 (y,x)에 있는 단어와 다른 경우. 이미 시작부터 글러먹은 경우. (첫글자부터 틀렸다)
    : 0을 리턴하며 그 값을 캐시에 저장한다.
    */
    if (word.at(wordIndex) != board[y][x]) {
        return ret = 0;
    }
 
    /*
    여기까지 왔다는 것은, 게임판에서 현재 위치 (y,x)에 내가 찾으려는 단어의 첫글자가 있다는 것이다.
    (비로소 시작할 수 있다)
    */
 
    wordIndex++;    // 다음 글자(character)를 찾기 위해, index++
 
    /*
    index 가 범위를 벗어난 경우 (방금 전 index에 해당하는 글자가 마지막 글자였던 것이다)
    그렇다면 원하는 글자를 다 찾은 것이므로
    : 1을 리턴하며 그 값을 캐시에 저장한다.
    */
    if (wordIndex >= word.size()) {
        return ret = 1;
    }
 
    /* 
    o o o
    o 나o
    o o o
    나(현재위치 y,x)를 기준으로 인접한 좌표 8개 모두를 재귀로 탐색한다.
    그 중에 하나라도 찾게 된다면 성공한 것이므로 OR 연산을 시킨다.
    : 결과적으로 0이나 1이 리턴되며 그 값을 캐시에 저장한다.
    */
    return ret = (
        canFindWord(y - 1, x - 1, wordIndex) || canFindWord(y - 1, x, wordIndex) || canFindWord(y - 1, x + 1, wordIndex)
        || canFindWord(y, x - 1, wordIndex) || canFindWord(y, x + 1, wordIndex)
        || canFindWord(y + 1, x - 1, wordIndex) || canFindWord(y + 1, x, wordIndex) || canFindWord(y + 1, x + 1, wordIndex)
        );
}
 
int main() {
    /* 테스트 케이스의 수 C */
    int C;
    scanf("%d\n", &C);
 
    for (int i = 0; i < C; i++) {
        /* 게임판 (board[5][5]) 생성 */
        for (int j = 0; j < 5; j++) {
            scanf("%c%c%c%c%c\n", &board[j][0], &board[j][1], &board[j][2], &board[j][3], &board[j][4]);
        }
 
        /* 찾을 단어의 수 N */
        int N;
        scanf("%d\n", &N);
 
        for (int j = 0; j < N; j++) {
            memset(cache, -1, sizeof(cache));    // 단어를 찾는 루프를 돌 때마다 캐시를 -1로 초기화해준다.
 
            /* 찾을 단어 word */
            word.clear();
            getline(cin, word);
 
            bool isFound = false;
 
            /*
            5X5 상의 모든 점을 대상으로 탐색한다.
            발견시 isFound = true 하며, 이중 break로 완전히 탈출
            */
            for (int k = 0; k < 5; k++) {
                for (int l = 0; l < 5; l++) {
                    if (canFindWord(k, l, 0) == 1) {
                        isFound = true;
                        break;
                    }
                }
                if (isFound) {
                    break;
                }
            }
 
            /* 결과에 따른 출력 */
            if (isFound) {
                cout << word << " YES" << endl;
            }
            else {
                cout << word << " NO" << endl;
            }
        }
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

외발뛰기(JUMPGAME) 정답 코드  (0) 2015.01.27
조세푸스 문제(JOSEPHUS) 정답 코드  (1) 2015.01.26
Longest Increasing Sequence(LIS) 정답 코드  (0) 2015.01.20
타일링(TILING2) 정답 코드  (0) 2015.01.17
삼각형 위의 최대 경로(TRIANGLEPATH) 정답 코드  (0) 2015.01.17

Intent 활용 예시

뿌리튼튼 CS/Android2014. 11. 12. 10:55

원본이 어딘지를 모르겠네요. 아무튼 퍼온 내용입니다.


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
// 웹페이지 띄우기
Uri uri = Uri.parse("http://www.google.com");
Intent it  = new Intent(Intent.ACTION_VIEW,uri);
startActivity(it);
 
 
// 구글맵 띄우기
Uri uri = Uri.parse("geo:38.899533,-77.036476");
Intent it = new Intent(Intent.Action_VIEW,uri);
startActivity(it);
 
 
// 구글 길찾기 띄우기
Uri uri = Uri.parse("http://maps.google.com/maps?f=d&saddr=출발지주소&daddr=도착지주소&hl=ko");
Intent it = new Intent(Intent.ACTION_VIEW,URI);
startActivity(it);
 
 
// 전화 걸기
Uri uri = Uri.parse("tel:xxxxxx");
Intent it = new Intent(Intent.ACTION_DIAL, uri);  
startActivity(it); 
 
 
Uri uri = Uri.parse("tel.xxxxxx");
Intent it = new Intent(Intent.ACTION_CALL,uri);
// 퍼미션을 잊지 마세요. 
 
 
// SMS/MMS 발송
Intent it = new Intent(Intent.ACTION_VIEW);   
it.putExtra("sms_body", "The SMS text");   
it.setType("vnd.android-dir/mms-sms");   
startActivity(it); 
 
 
// SMS 발송
Uri uri = Uri.parse("smsto:0800000123");   
Intent it = new Intent(Intent.ACTION_SENDTO, uri);   
it.putExtra("sms_body", "The SMS text");   
startActivity(it); 
 
 
// MMS 발송
Uri uri = Uri.parse("content://media/external/images/media/23");   
Intent it = new Intent(Intent.ACTION_SEND);   
it.putExtra("sms_body", "some text");   
it.putExtra(Intent.EXTRA_STREAM, uri);   
it.setType("image/png");   
startActivity(it);
 
 
// 이메일 발송1 : 이메일앱에 (받는 사람의 주소)만 넣어주며 실행
Uri uri = Uri.parse("mailto:xxx@abc.com");
Intent it = new Intent(Intent.ACTION_SENDTO, uri);
startActivity(it);
 
// 이메일 발송2 : 이메일앱에 (받는 사람의 주소, 제목, 내용)을 넣어주며 실행
Intent it = new Intent(Intent.ACTION_SEND);   
it.putExtra(Intent.EXTRA_EMAIL, "me@abc.com");
it.putExtra(Intent.EXTRA_SUBJECT, "The email subject text");
it.putExtra(Intent.EXTRA_TEXT, "The email body text");
it.setType("text/plain");   
startActivity(Intent.createChooser(it, "Choose Email Client")); 
 
 
// 미디어파일 플레이 하기
Intent it = new Intent(Intent.ACTION_VIEW);
Uri uri = Uri.parse("file:///sdcard/song.mp3");
it.setDataAndType(uri, "audio/mp3");
startActivity(it);
 
 
Uri uri = Uri.withAppendedPath(
  MediaStore.Audio.Media.INTERNAL_CONTENT_URI, "1");   
Intent it = new Intent(Intent.ACTION_VIEW, uri);   
startActivity(it); 
 
 
// 설치 어플 제거
Uri uri = Uri.fromParts("package", strPackageName, null);   
Intent it = new Intent(Intent.ACTION_DELETE, uri);   
startActivity(it);
 
 
// APK파일을 통해 제거하기
Uri uninstallUri = Uri.fromParts("package", "xxx", null);
returnIt = new Intent(Intent.ACTION_DELETE, uninstallUri);
 
 
// APK파일 설치
Uri installUri = Uri.fromParts("package", "xxx", null);
returnIt = new Intent(Intent.ACTION_PACKAGE_ADDED, installUri);
 
 
// 음악 파일 재생
Uri playUri = Uri.parse("file:///sdcard/download/everything.mp3");
returnIt = new Intent(Intent.ACTION_VIEW, playUri);
 
 
// 마켓에서 어플리케이션 검색
Uri uri = Uri.parse("market://search?q=pname:pkg_name");  
Intent it = new Intent(Intent.ACTION_VIEW, uri);  
startActivity(it);  
// 패키지명은 어플리케이션의 전체 패키지명을 입력해야 합니다.
 
 
// 마켓 어플리케이션 상세 화면
Uri uri = Uri.parse("market://details?id=어플리케이션아이디");  
Intent it = new Intent(Intent.ACTION_VIEW, uri);  
startActivity(it);
// 아이디의 경우 마켓 퍼블리싱사이트의 어플을 선택후에 URL을 확인해보면 알 수 있습니다.
 
 
// 구글 검색
Intent intent = new Intent();
intent.setAction(Intent.ACTION_WEB_SEARCH);
intent.putExtra(SearchManager.QUERY,"searchString")
startActivity(intent);
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Android' 카테고리의 다른 글

Android Studio에서 Library 추가시 쓸데없는 Duplicate 오류 대처법  (0) 2015.06.12
[강좌] 초급2 - 버튼 클릭 + 리스너  (0) 2015.02.15
[강좌] Android SDK Search - 설치 및 SDK 소스 보기  (0) 2015.01.17
[강좌] 초급1 - 입문 + xml, java 파일 작성법  (0) 2015.01.16
투명색 RGB 코드  (0) 2014.11.12

투명색 RGB 코드

뿌리튼튼 CS/Android2014. 11. 12. 10:39

#00ff0000


색 코드를 넣을 수 있는 아무 곳에나 넣으면 된다.


주로


<...

android:background="#00ff0000"

.../>


의 형태로 많이 쓰인다.

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Android' 카테고리의 다른 글

Android Studio에서 Library 추가시 쓸데없는 Duplicate 오류 대처법  (0) 2015.06.12
[강좌] 초급2 - 버튼 클릭 + 리스너  (0) 2015.02.15
[강좌] Android SDK Search - 설치 및 SDK 소스 보기  (0) 2015.01.17
[강좌] 초급1 - 입문 + xml, java 파일 작성법  (0) 2015.01.16
Intent 활용 예시  (0) 2014.11.12

티스토리툴바