(윤성우 저, 'TCP/IP 소켓 프로그래밍' - 11장 관련 내용입니다)


책에 기술 된 Multiplexing 서버와 Multiprocessing 클라이언트를 일부 수정하여 채팅 프로그램을 작성하는 문제입니다.
다중 접속을 지원하고 다중 접속 시 카카오톡 단체채팅방처럼 한 사람의 대화를 모든 사람이 보도록 구현하였습니다.


아래는 Multiplexing 서버를 수정한 채팅 서버 코드입니다.
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <sys/socket.h>
#include <sys/time.h>
#include <sys/select.h>
 
#define BUF_SIZE 100
void error_handling(char *buf);
 
int main(int argc, char *argv[])
{
    //소켓, timeout값, fd_set값 등을 저장할 변수 선언
    int serv_sock, clnt_sock;
    struct sockaddr_in serv_adr, clnt_adr;
    struct timeval timeout;
    fd_set reads, cpy_reads;
    socklen_t adr_sz;
    int fd_max, str_len, fd_num, i;
    char buf[BUF_SIZE];
 
    //입력 포맷이 맞지 않으면 오류 출력 후 종료
    if(argc!=2) {
        printf("Usage : %s <port>\n", argv[0]);
        exit(1);
    }
 
    //서버의 소켓을 생성
    serv_sock=socket(PF_INET, SOCK_STREAM, 0);
    
    //서버의 주소정보를 저장, 이때 네트워크 바이트 순서로 저장한다
    memset(&serv_adr, 0sizeof(serv_adr));
    serv_adr.sin_family=AF_INET;
    serv_adr.sin_addr.s_addr=htonl(INADDR_ANY);
    serv_adr.sin_port=htons(atoi(argv[1]));
    
    //bind 함수를 통해 소켓에 서버의 주소정보를 할당
    if(bind(serv_sock, (struct sockaddr*&serv_adr, sizeof(serv_adr))==-1)
        error_handling("bind() error");
 
    //연결 대기 상태로 진입
    if(listen(serv_sock, 5)==-1)
        error_handling("listen() error");
 
    //fd_set형 변수 reads의 모든 비트를 0으로 초기화
    FD_ZERO(&reads);
    //소켓 디스크립터 정보를 등록
    FD_SET(serv_sock, &reads);
    //소켓의 번호를 저장
    fd_max=serv_sock;
 
    while(1) {
        cpy_reads=reads;
        //타임아웃 시간 설정
        timeout.tv_sec=5;
        timeout.tv_usec=5000;
        
        //소켓 포함 모든 파일디스크립터를 대상으로 '수신된 데이터의 존재여부' 검사
            //오류가 발생했다면
        if((fd_num=select(fd_max+1&cpy_reads, 00&timeout))==-1) {
            break;
        }
            //Timeout이 발생했다면
        if(fd_num==0) {
            continue;
        }
            //변화가 발생했다면
        for(i=0; i<fd_max+1; i++) {
            if(FD_ISSET(i, &cpy_reads)) {
                // 연결요청이 발생했다면
                if(i==serv_sock) {
                    //연결요청 수락    
                    adr_sz=sizeof(clnt_adr);
                    clnt_sock=accept(serv_sock, (struct sockaddr*)&clnt_adr, &adr_sz);
                    
                    //해당 연결을 감시하도록 FD_SET을 통해 설정
                    FD_SET(clnt_sock, &reads);
                    //연결을 통해 clnt_sock 값이 증가했다면 fd_max 재설정
                    //(연결종료 된 클라이언트 < 새로 연결된 클라이언트)이라면 
                    if(fd_max<clnt_sock)
                        fd_max=clnt_sock;
                    printf("connected client: %d \n", clnt_sock);
                }
                else {
                    //메세지를 읽어들임   
                    str_len=read(i, buf, BUF_SIZE);
                    //종료 요청이 왔다면 연결 종료, fd_set값 초기화, 해당 소켓 종료
                    if(str_len==0) {    
                        FD_CLR(i, &reads);
                        close(i);
                        printf("closed client: %d \n", i);
                    }
                    //메세지가 왔다면
                    else {
                        //write(i, buf, str_len);    // echo!
                        //메세지를 모든 사람에게 전송 (4가 첫번째 소켓)
                        for(int j=4; j < fd_max + 1; j++) { 
                            write(j, buf, str_len);
                        }
                    }
                }
            }
        }
    }
    close(serv_sock);
    return 0;
}
 
void error_handling(char *buf) {
    fputs(buf, stderr);
    fputc('\n', stderr);
    exit(1);
}




아래는 Multiprocessing 클라이언트를 수정한 채팅 클라이언트 코드입니다.
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <sys/socket.h>
 
#define BUF_SIZE 100
#define NAME_SIZE 20
 
void error_handling(char *message);
void read_routine(int sock, char *buf);
void write_routine(int sock, char *buf);
 
char name[NAME_SIZE] = "[NULL]";
char buf[BUF_SIZE];
 
int main(int argc, char *argv[]) {
    //소켓, pid값 등을 저장할 변수선언
    int sock;
    pid_t pid;
    char buf[BUF_SIZE];
    struct sockaddr_in serv_adr;
    
    //입력 포맷이 맞지 않으면 오류 출력 후 종료
    if(argc!=4) {    
        printf("Usage : %s <IP> <port> <name>\n", argv[0]);
        exit(1);
    }
    //데이터를 형식에 맞추어 쓰드록 지정
    sprintf(name, "[%s]", argv[3]);
 
    //클라이언트 소켓 설정
    sock=socket(PF_INET, SOCK_STREAM, 0);  
    memset(&serv_adr, 0sizeof(serv_adr));
    serv_adr.sin_family=AF_INET;
    serv_adr.sin_addr.s_addr=inet_addr(argv[1]);
    serv_adr.sin_port=htons(atoi(argv[2]));
    
    //connect함수를 통해 서버와 연결 시도
    if(connect(sock, (struct sockaddr*)&serv_adr, sizeof(serv_adr))==-1)
        error_handling("connect() error!");
 
    //fork 함수를 통해 입력, 출력을 처리하는 프로세스를 각각 만듦 
    pid=fork();
    if(pid==0)
        write_routine(sock, buf);
    else 
        read_routine(sock, buf);
 
    close(sock);
    return 0;
}
 
//서버로부터 메세지를 읽어들이는 함수
void read_routine(int sock, char *buf) {
    char total_msg[NAME_SIZE + BUF_SIZE];
    while(1) {
        //서버로부터 메세지를 읽어들임
        int str_len=read(sock, total_msg, NAME_SIZE + BUF_SIZE);
        
        //close를 받았다면 종료
        if(str_len==0)
            return;
 
        //데이터 출력
        total_msg[str_len]=0;
        fputs(total_msg, stdout);
        //printf("Message from server: %s", buf);
    }
}
 
//서버로 메세지를 전송하는 함수
void write_routine(int sock, char *buf) {
    char total_msg[NAME_SIZE + BUF_SIZE];
    while(1) {
        //입력값을 받아들임
        fgets(buf, BUF_SIZE, stdin);
        
        //만약 'q'나 'Q' 문자가 입력되면 종료 
        if(!strcmp(buf,"q\n"|| !strcmp(buf,"Q\n")) {    
            shutdown(sock, SHUT_WR);
            return;
        }
        
        //데이터를 형식에 맞추어 쓰드록 지정
        sprintf(total_msg, "%s %s", name, buf);
        
        //서버로 입력한 데이터 전송
        write(sock, total_msg, strlen(total_msg));
    }
}
 
void error_handling(char *message) {
    fputs(message, stderr);
    fputc('\n', stderr);
    exit(1);
}



(윤성우 저, 'TCP/IP 소켓 프로그래밍' - 10장 관련 내용입니다)


Select 함수를 이용하여 주어진 서버와 통신하는 I/O 멀티플렉싱 클라이언트를 작성하는 문제입니다.


 - 일정 시간 내에 데이터를 입력하지 않을 경우 Time Out 메시지 출력

 - read_routine 함수와 write_routine함수 적절히 호출


아래는 주어진 서버(multi_serv.c) 코드입니다.

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <sys/socket.h>
#include <sys/time.h>
#include <sys/select.h>
 
#define BUF_SIZE 100
void error_handling(char *buf);
 
int main(int argc, char *argv[])
{
    int serv_sock, clnt_sock;
    struct sockaddr_in serv_adr, clnt_adr;
    struct timeval timeout;
    fd_set reads, cpy_reads;
 
    socklen_t adr_sz;
    int fd_max, str_len, fd_num, i;
    char buf[BUF_SIZE];
    if(argc!=2) {
        printf("Usage : %s <port>\n", argv[0]);
        exit(1);
    }
 
    serv_sock=socket(PF_INET, SOCK_STREAM, 0);
    memset(&serv_adr, 0sizeof(serv_adr));
    serv_adr.sin_family=AF_INET;
    serv_adr.sin_addr.s_addr=htonl(INADDR_ANY);
    serv_adr.sin_port=htons(atoi(argv[1]));
    
    if(bind(serv_sock, (struct sockaddr*&serv_adr, sizeof(serv_adr))==-1)
        error_handling("bind() error");
    if(listen(serv_sock, 5)==-1)
        error_handling("listen() error");
 
    FD_ZERO(&reads);
    FD_SET(serv_sock, &reads);
    fd_max=serv_sock;
 
    while(1)
    {
        cpy_reads=reads;
        timeout.tv_sec=5;
        timeout.tv_usec=5000;
 
        if((fd_num=select(fd_max+1&cpy_reads, 00&timeout))==-1)
            break;
        
        if(fd_num==0)
            continue;
 
        for(i=0; i<fd_max+1; i++)
        {
            if(FD_ISSET(i, &cpy_reads))
            {
                if(i==serv_sock)     // connection request!
                {
                    adr_sz=sizeof(clnt_adr);
                    clnt_sock=
                        accept(serv_sock, (struct sockaddr*)&clnt_adr, &adr_sz);
                    FD_SET(clnt_sock, &reads);
                    if(fd_max<clnt_sock)
                        fd_max=clnt_sock;
                    printf("connected client: %d \n", clnt_sock);
                }
                else    // read message!
                {
                    str_len=read(i, buf, BUF_SIZE);
                    if(str_len==0)    // close request!
                    {
                        FD_CLR(i, &reads);
                        close(i);
                        printf("closed client: %d \n", i);
                    }
                    else
                    {
                        write(i, buf, str_len);    // echo!
                    }
                }
            }
        }
    }
    close(serv_sock);
    return 0;
}
 
void error_handling(char *buf)
{
    fputs(buf, stderr);
    fputc('\n', stderr);
    exit(1);
}




주어진 multi_server 코드에 맞는 echo_client를 구현하기 위해 아래와 같은 코드를 작성했습니다.


코드 설명입니다.

1. 먼저 서버와 통신하기 위한 기본적인 과정을 거칩니다. (socket 만들고 connect)

2. select함수를 사용하기 위해 초기화와 타임아웃 값 설정 과정을 거칩니다.

3. select함수를 이용하여 입력 디스크립터(0번)과 소켓 디스크립터를 감시하여 수신된 데이터의 존재 여부를 검사합니다.

4. 수신된 데이터의 없다면 "Time-out!"을 출력하고 수신된 데이터가 있다면 입력, 출력 여부에 맞게 처리해줍니다.


아래는 구현한 echo_client 코드입니다.

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <sys/socket.h>
#include <sys/time.h>
#include <sys/select.h>
 
#define BUF_SIZE 30
void error_handling(char *message);
void read_routine(int sock, char *buf);
void write_routine(int sock, char *buf);
 
int main(int argc, char *argv[]) {
    int sock;
    char buf[BUF_SIZE];
    struct sockaddr_in serv_adr;
 
    //타이머를 계산하기 위해 timeval형 변수 timeout 설정
    struct timeval timeout;
    //fd_set형 변수 선언하여 파일 디스크립터 정보 등록
    fd_set reads, cpy_reads;
    //검사할 파일 디스크립터의 수
    int fd_max, fd_num;
 
    if(argc!=3) {
        printf("Usage : %s <IP> <port>\n", argv[0]);
        exit(1);
    }
 
    sock=socket(PF_INET, SOCK_STREAM, 0);
    memset(&serv_adr, 0sizeof(serv_adr));
    serv_adr.sin_family=AF_INET;
    serv_adr.sin_addr.s_addr=inet_addr(argv[1]);
    serv_adr.sin_port=htons(atoi(argv[2]));
 
    if(connect(sock, (struct sockaddr*)&serv_adr, sizeof(serv_adr))==-1)
        error_handling("connect() error!");
 
    //fd_set형 변수 reads의 모든 비트를 0으로 초기화
    FD_ZERO(&reads);
    //입력 및 소켓 디스크립터 정보를 등록
    FD_SET(0&reads);
    FD_SET(sock, &reads);
    //소켓의 번호를 저장
    fd_max = sock;
    while(1) {
        cpy_reads = reads;
        //타임아웃 시간 설정
        timeout.tv_sec=5;
        timeout.tv_usec=0;
        //소켓 포함 모든 파일디스크립터를 대상으로 '수신된 데이터의 존재여부' 검사
        fd_num=select(fd_max+1&cpy_reads, 00&timeout);
        //오류가 발생했다면
        if(fd_num==-1) {
            error_handling("select() error\n");
        }
        //Timeout이 발생했다면
        else if (fd_num == 0) {
            puts("Time-out!");
            continue;
        }
        //변화가 발생했다면
        else {
            //만약 입력 디스크립터에 변화가 발생했다면 (사용자로부터 데이터를 입력받았다면)
            if(FD_ISSET(0&cpy_reads)) {
                //입력된 내용을 서버로 전송하는 함수
                write_routine(sock, buf);
                //파일 디스크립터 정보 삭제
                FD_CLR(0&cpy_reads);
            }
            //만약 포트에 변화가 발생했다면(서버로부터 데이터를 받았다면)
            if(FD_ISSET(sock, &cpy_reads)) {
                //받은 데이터를 출력하는 함수
                read_routine(sock, buf);
                //파일 디스크립터 정보 삭제
                FD_CLR(sock, &cpy_reads);
            }
        }
    }
    close(sock);
    return 0;
}
 
void read_routine(int sock, char *buf)
{
    int str_len=read(sock, buf, BUF_SIZE);
    if(str_len==0)
        return;
 
    buf[str_len]=0;
    printf("Message from server: %s", buf);
}

void write_routine(int sock, char *buf)
{
    fgets(buf, BUF_SIZE, stdin);
    if(!strcmp(buf,"q\n"|| !strcmp(buf,"Q\n"))
    {
        shutdown(sock, SHUT_WR);
        exit(0);
    }
    write(sock, buf, strlen(buf));
}

void error_handling(char *message)
{
    fputs(message, stderr);
    fputc('\n', stderr);
    exit(1);
}


(윤성우 저, 'TCP/IP 소켓 프로그래밍' - 4장 관련 내용입니다)


echo_client 코드가 주어질 때, 주어진 클라이언트의 IP Address와 Port 번호를 출력하는 Iterative Echo Server를 만드는 문제입니다.


아래는 echo_client 코드입니다.

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <sys/socket.h>
 
#define BUF_SIZE 1024
void error_handling(char *message);
 
int main(int argc, char *argv[])
{
    int sock;
    char message[BUF_SIZE];
    int str_len;
    struct sockaddr_in serv_adr;
 
    if(argc!=3) {
        printf("Usage : %s <IP> <port>\n", argv[0]);
        exit(1);
    }
    
    sock=socket(PF_INET, SOCK_STREAM, 0);   
    if(sock==-1)
        error_handling("socket() error");
    
    memset(&serv_adr, 0sizeof(serv_adr));
    serv_adr.sin_family=AF_INET;
    serv_adr.sin_addr.s_addr=inet_addr(argv[1]);
    serv_adr.sin_port=htons(atoi(argv[2]));
    
    if(connect(sock, (struct sockaddr*)&serv_adr, sizeof(serv_adr))==-1)
        error_handling("connect() error!");
    else
        puts("Connected...........");
    
    while(1
    {
        fputs("Input message(Q to quit): ", stdout);
        fgets(message, BUF_SIZE, stdin);
        
        if(!strcmp(message,"q\n"|| !strcmp(message,"Q\n"))
            break;
 
        write(sock, message, strlen(message));
        str_len=read(sock, message, BUF_SIZE-1);
        message[str_len]=0;
        printf("Message from server: %s", message);
    }
    
    close(sock);
    return 0;
}
 
void error_handling(char *message)
{
    fputs(message, stderr);
    fputc('\n', stderr);
    exit(1);
}




주어진 echo_client 코드에 맞는 echo_server를 구현하기 위해 아래와 같은 코드를 작성했습니다.

(코드에서 해당되는 모든 부분에 주석으로 설명을 달았습니다. 아래 코드를 보고 이해가 안 된다면 가장 위에 언급된 책 4장을 참고하시기 바랍니다.)

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
//헤더 부분입니다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <sys/socket.h>
 
#define BUF_SIZE 1024
void error_handling(char *message);
 
//main함수
int main(int argc, char *argv[])
{
    int serv_sock, clnt_sock;        //서버와 클라이언트 소켓을 저장할 변수 선언
    char message[BUF_SIZE];            //메세지를 저장할 변수 선언
    int str_len, i;
 
    //서버와 클라이언트 주소정보를 저장할 구조체 변수 선언
    struct sockaddr_in serv_adr;
    struct sockaddr_in clnt_adr;
    socklen_t clnt_adr_sz;
 
  //입력값 올바르지 않다면 에러
    if(argc!=2) {
        printf("Usage : %s <port>\n", argv[0]);
        exit(1);
    }
 
    //서버의 소켓을 생성
    serv_sock=socket(PF_INET, SOCK_STREAM, 0);
    if(serv_sock==-1)
        error_handling("socket() error");
 
    //서버의 주소정보를 저장, 이때 네트워크 바이트 순서로 저장한다
    memset(&serv_adr, 0sizeof(serv_adr));
    serv_adr.sin_family=AF_INET;
    serv_adr.sin_addr.s_addr=htonl(INADDR_ANY);
    serv_adr.sin_port=htons(atoi(argv[1]));
 
    //bind 함수를 통해 소켓에 서버의 주소정보를 할당
    if(bind(serv_sock, (struct sockaddr*)&serv_adr, sizeof(serv_adr))==-1)
        error_handling("bind() error");
 
    //연결 대기 상태로 진입
    if(listen(serv_sock, 5)==-1)
        error_handling("listen() error");
 
    clnt_adr_sz=sizeof(clnt_adr);
 
    for(i=0; i<5; i++)
    {
        //클라이언트로 부터 연결 요청이 오면 수락한다. 이때 클라이언트의 주소 정보를 저장한다.
        clnt_sock=accept(serv_sock, (struct sockaddr*)&clnt_adr, &clnt_adr_sz);
        if(clnt_sock==-1)
            error_handling("accept() error");
        else {
            /*
            클라이언트의 IP를 출력하기 위해 구조체 clnt_adr의 인자 sin_addr에 저장된 IP주소를 참조.
            이때 32비트 정수 자료형으로 저장 된 IP 주소를 네트워크 바이트 순서로 바꾸어
            OOO.OOO.OOO.OOO 형태의 문자열로 출력하기 위해 inet_ntoa 함수를 이용한다.
            */
            printf("Client's IP : %s\n",inet_ntoa(clnt_adr.sin_addr));
 
            /*
            클라이언트의 Port번호를 출력하기 위해 구조체 clnt_adr의 인자 sin_port에 저장된
            Port번호를 참조. 이때 Big Endian 방식으로 저장 된 포트 번호를 네트워크 바이트 순서로
            정렬해서 반환하기 위해 ntohs 함수를 이용한다.
            */
            printf("Client's Port : %d\n",ntohs(clnt_adr.sin_port));
 
            printf("Connected client %d \n", i+1);
        }
        //버퍼를 다 읽어와 이를 출력한다. 클라이언트가 종료 요청시에 while문을 탈출한다.
        while((str_len=read(clnt_sock, message, BUF_SIZE))!=0)
            write(clnt_sock, message, str_len);
 
        //클라이언트 소켓의 종료를 받아들인다.
        close(clnt_sock);
    }
  //서버 소켓의 종료
    close(serv_sock);
    return 0;
}
 
//에러 처리
void error_handling(char *message)
{
    fputs(message, stderr);
    fputc('\n', stderr);
    exit(1);
}
 



Backjoon Online Judge 

"2178번 : 미로탐색" 문제입니다.


문제 링크 : https://www.acmicpc.net/problem/2178


'2178번 : 미로탐색' 문제의 경우 BFS로 문제를 해결했습니다.

이전에 풀었던 '7576번 : 토마토' 문제의 코드를 살짝 변경하여 해결했습니다.

(참고링크 : http://rehu.tistory.com/20)



문제 및 코드 설명입니다.


먼저 미로의 상태를 저장하기 위해 2차원 배열로 미로를 저장했습니다.

이때 BFS를 쉽게 구현하기 위해 큐를 pair로 선언하여 x좌표, y좌표를 저장했습니다.

또 미로의 상태를 연속된 숫자로 입력받으므로 일반적인 입력으로는 미로에 숫자를 하나씩 저장할 수 없습니다.

char형 배열을 통해 문자로 입력받고 ASCII 변환을 이용하여 숫자를 배열에 하나씩 저장했습니다. 


이후 시작점에서부터 상하좌우에 길이 있는지 확인하고 길이 있다면 이동횟수를 길에 저장하도록 했습니다.

(시작점의 경우 1로 설정하면 한칸 이동했다가 다시 시작점 방향으로 탐색하기 때문에 0으로 초기화 했습니다.

 물론 시작점 방향으로 탐색하면 곧 탐색이 종료되기에 초기화 과정 없이도 정답이 나오긴 합니다.)


미로의 시작점과 끝 점은 가장 멀리 있으므로 큐의 모든 원소가 사라질때까지 반복했으며, BFS 탐색 후 도착점의 값을 출력해 주었습니다.


코드는 C++로 작성하였습니다.

(단, 큐를 pair을 이용해 구현하여 C++ 11 이상에서만 정상작동 합니다.

 C++ 11 이하에서 작동되기를 원하시면 큐를 pair로 구현하는 대신 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
#include <iostream>
#include <queue>
 
#define Max 100
 
using namespace std;
 
int main() {
    int M, N, x, y, tx, ty;
    char tmp[Max];
    int maze[Max][Max] = { 0, };
    int result = 0;
    queue<pair<intint>> q;
 
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> tmp;
        for (int j = 0; j < M; j++) {
            maze[i][j] = tmp[j] - 48;
        }
    }
    maze[0][0= 0;
 
    q.push(make_pair(00));
    int side[4= { 10-10 };
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
 
        if (maze[x][y] == 2 + result)
            result++;
 
        for (int i = 0; i < 4; i++) {
            tx = x - side[i];
            ty = y - side[3 - i];
            if (0 <= tx && tx < N && 0 <= ty && ty < M) {
                if (maze[tx][ty] == 1) {
                    maze[tx][ty] = 2 + result;
                    q.push(make_pair(tx, ty));
                }
            }
        }
        q.pop();
    }
 
    cout << maze[N-1][M-1<< endl;
    cin >> N;
}
 



'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글

2667번 : 단지번호붙이기  (0) 2018.05.29
2606번 : 바이러스  (0) 2018.05.28
7569번 : 토마토  (0) 2018.05.17
7576번 : 토마토  (0) 2018.05.16
2293번 : 동전 1  (0) 2018.05.15

Backjoon Online Judge 

"7569번 : 토마토" 문제입니다.


문제 링크 : https://www.acmicpc.net/problem/7569



이전에 풀었던 '7576번 : 토마토' 문제에서 상자를 층으로 쌓는 기능만 추가된 문제입니다.

'7576번 : 토마토' 문제를 먼저 해결하고 온다면 현재 문제인 '7569번 : 토마토'는 쉽게 해결가능하다고 봅니다.

(참고링크 : http://rehu.tistory.com/20)


코드 부분도 "7576번 : 토마토" 문제에서 달라진 부분이 거의 없습니다.

아래 코드를 보고 비교한다면 쉽게 이해할 수 있을 것입니다.



코드는 C++로 작성하였습니다.

(단, 큐를 pair을 이용해 구현하여 C++ 11 이상에서만 정상작동 합니다.

 C++ 11 이하에서 작동되기를 원하시면 큐를 pair로 구현하는 대신 3개를 만들면 됩니다.)

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
#include <iostream>
#include <queue>
 
#define Max 100
 
using namespace std;
typedef pair<intpair<intint>> pair3;
 
int main() {
    int M, N, H, x, y, z, tx, ty, tz;
    int box[Max][Max][Max] = { 0, };
    int result = 0;
    queue<pair3> q;
 
    cin >> M >> N >> H;
    for (int k = 0; k < H; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                cin >> box[i][j][k];
                if (box[i][j][k] == 1) {
                    q.push({ i,{j,k} });
                }
            }
        }
    }
 
    int side[6= { 100-10 ,0 };
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second.first;
        z = q.front().second.second;
 
        if (box[x][y][z] == 2 + result)
            result++;
 
        for (int i = 0; i < 6; i++) {
            tx = x - side[i];
            ty = y - side[(i + 1) % 6];
            tz = z - side[(i + 2) % 6];
            if (0 <= tx && tx < N && 0 <= ty && ty < M && 0 <= tz && tz < H) {
                if (box[tx][ty][tz] == 0) {
                    box[tx][ty][tz] = 2 + result;
                    q.push(make_pair(tx, make_pair(ty, tz)));
                }
            }
        }
        q.pop();
    }
 
    for (int k = 0; k < H; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                    if (box[i][j][k] == 0) {
                        result = -1;
                        break;
                }
            }
        }
    }
    cout << result << endl;
}
 



'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글

2606번 : 바이러스  (0) 2018.05.28
2178번 : 미로탐색  (0) 2018.05.17
7576번 : 토마토  (0) 2018.05.16
2293번 : 동전 1  (0) 2018.05.15
10844번 : 쉬운 계단 수  (0) 2018.05.13